03-Merge Sort
I. What is merge sort?
Merge sort is a divide-and-conquer algorithm that splits an array into
smaller subarrays, sorts them, and merges them back together.
II. How to implement merge sort?
#include <iostream>
#include <vector>
// Function to merge two sorted subarrays
void merge(std::vector<int>& arr, int left, int mid, int right)
{
int n1 {mid - left + 1}; // Size of left subarray
int n2 {right - mid}; // Size of right subarray
// Create temporary arrays
std::vector<int> L(n1);
std::vector<int> R(n2);
// Copy data to temporary arrays
for (int i {0}; i < n1; i++)
L[i] = arr[left + i];
for (int j {0}; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge the temporary arrays back into arr[left..right]
int i {0};
int j {0};
int k {left};
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements of L[] (if any)
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[] (if any)
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Recursive function to perform merge sort
void mergeSort(std::vector<int>& arr, int left, int right)
{
if (left >= right) // Base case
return;
int mid {left + (right - left) / 2}; // Avoids overflow for
large left and right
// Divide: Sort the first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Conquer: Merge the sorted halves
merge(arr, left, mid, right);
}
// Function to print the array
void printArray(const std::vector<int>& arr)
{
for (int i {0}; i < [Link](); i++)
{
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main()
{
std::vector<int> arr {6, 5, 12, 10, 9, 1};
int n {static_cast<int>([Link]())};
std::cout << "Original array: ";
printArray(arr);
// Perform merge sort
mergeSort(arr, 0, n - 1);
std::cout << "Sorted array: ";
printArray(arr);
return 0;
}
2.1 Merge() function
This is the thought process on how to implement merge() using 2
pointers technique.
Copy the remaining elements from the first array to main subarray.
Copy the remaining elements from the first array to main subarray (this
doesn't has any left-over elements).
This is the thought process of how merge sort works.
mergeSort(arr, 0, 5)
├── mergeSort(arr, 0, 2)
│ ├── mergeSort(arr, 0, 0) → Base case
│ ├── mergeSort(arr, 1, 2)
│ │ ├── mergeSort(arr, 1, 1) → Base case
│ │ └── mergeSort(arr, 2, 2) → Base case
│ │ └── Merge [5] and [12] → [5, 12]
│ └── Merge [6] and [5, 12] → [5, 6, 12]
├── mergeSort(arr, 3, 5)
│ ├── mergeSort(arr, 3, 3) → Base case
│ ├── mergeSort(arr, 4, 5)
│ │ ├── mergeSort(arr, 4, 4) → Base case
│ │ └── mergeSort(arr, 5, 5) → Base case
│ │ └── Merge [9] and [1] → [1, 9]
│ └── Merge [10] and [1, 9] → [1, 9, 10]
└── Merge [5, 6, 12] and [1, 9, 10] → [1, 5, 6, 9, 10, 12]
III. Why should we use merge sort?
3.1 Time Complexity
Merge Sort has a consistent time complexity of O(n log n) in all cases:
Best case: O(nlogn)
Average case: O(nlogn)
Worst case: O(nlogn)
This makes it much faster than simpler algorithms like Bubble Sort
O(n²) or Insertion Sort O(n²) for large datasets.
3.2 Best usage
1. Large datasets: When you need to sort a large amount of data efficiently.
2. Stability is important: When you need to preserve the order of equal
elements.
3. Linked lists: When sorting linked lists.
4. External sorting: When sorting data stored on disk or other external
storage.