Merge Sort in C++
What is Merge Sort in C++?
Merge sort is one the sorting technique that is used to sort the data in a logical order. It uses divide and conquer approach for sorting the data. Merge sort repeatedly breaks down a list into several sub lists until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list. In this article, we will read more about merge sort in C++.
| Time Complexity | Θ(n Log n) |
| Best Case | Ω(n Log n) |
| Worst Case | O(n Log n) |
| Space Complexity | O(n) |
Merge Sort in C++
- A file of any size can be sorted using merge sort.
- Elements in the merge sort are divided into two sub list again and again until each sub-list contain only one element.
- After this, the elements are merged to make a sorted list.
- It requires more space and is less efficient
Execution of Merge sort in C++
Merge sort is executed in three steps:-
1.) Divide Step:
First of all the array will be divide in to N sub list, until each sub list contains only one element.
2.) Conquer Step:
Take two sub list and place them in logical order.
3.) Combine Step:
Combine the elements back by merging the two sorted sub list into a sorted sequence.
Program for merge sort in C++
We will look at two different methods, both have the same time complexity with the difference that –
- Method 1 – Uses two temp subarrays
- Method 2 – Uses 1 temp subarray
The combined size of two temp subarrays in method 1 is the same as the whole array in method 2. So the space complexity remains the same.
#include<iostream> using namespace std; void mergeSort(int[],int,int); void merge(int[],int,int,int); void printArray(int arr[], int size){ int i; for(i = 0; i < size; i++){ cout << arr[i] << " "; } cout << endl; } int main() { int array[]= {8, 4, 5, 1, 3, 9, 0, 2, 7, 6}; int i; int size = sizeof(array)/sizeof(array[0]); printArray(array, size); mergeSort(array, 0, size-1); printArray(array, size); } void mergeSort(int a[], int left, int right) { int mid; if(left < right) { // can also use mid = left + (right - left) / 2 // this can avoid data type overflow mid = (left + right)/2; // recursive calls to sort first half and second half subarrays mergeSort(a, left, mid); mergeSort(a, mid + 1, right); merge(a, left, mid, right); } } void merge(int arr[], int left, int mid, int right) { int i, j, k; int n1 = mid - left + 1; int n2 = right - mid; // create temp arrays to store left and right subarrays int L[n1], R[n2]; // Copying data to temp arrays L[] and R[] for (i = 0; i < n1; i++) L[i] = arr[left + i]; for (j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; // here we merge the temp arrays back into arr[l..r] i = 0; // Starting index of L[i] j = 0; // Starting index of R[i] k = left; // Starting index of merged subarray while (i < n1 && j < n2) { // place the smaller item at arr[k] pos if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // Copy the remaining elements of L[], if any while (i < n1) { arr[k] = L[i]; i++; k++; } // Copy the remaining elements of R[], if any while (j < n2) { arr[k] = R[j]; j++; k++; } }
Output
8 4 5 1 3 9 0 2 7 6 0 1 2 3 4 5 6 7 8 9
#include<iostream> using namespace std; void mergeSort(int[],int,int); void merge(int[],int,int,int); void printArray(int arr[], int size){ int i; for(i = 0; i < size; i++){ cout << arr[i] << " "; } cout << endl; } int main() { int array[]= {8, 4, 5, 1, 3, 9, 0, 2, 7, 6}; int i; int size = sizeof(array)/sizeof(array[0]); printArray(array, size); mergeSort(array, 0, size-1); printArray(array, size); } void mergeSort(int a[], int left, int right) { int mid; if(left < right) { // can also use mid = left + (right - left) / 2 // this can avoid data type overflow mid = (left + right)/2; // recursive calls to sort first half and second half subarrays mergeSort(a, left, mid); mergeSort(a, mid + 1, right); merge(a, left, mid, right); } } void merge(int a[], int left, int mid, int right) { int i = left; // starting index of left subarray int j = mid + 1; // starting index of right subarray int index = left; // used to place items in temp[] int temp[10]; while(i<=mid && j<=right) { // place the smaller item at temp[index] if(a[i] < a[j]) { temp[index] = a[i]; i = i+1; } else { temp[index] = a[j]; j = j+1; } index++; } // i > mid would mean all items for left // subarray were successfully placed, and there // must be unplaced right subarray items if(i>mid) { while(j<=right) { temp[index] = a[j]; index++; j++; } } // else all items of right subarray must have // been placed and there must be // unplaced items in the left-subarray else { while(i<=mid) { temp[index] = a[i]; index++; i++; } } int p = left; // left index of subarray // by now index would have reached right // most index of right subarray // placing all items of temp[] into actual array a[] while(p < index) { a[p]=temp[p]; p++; } }
Output
8 4 5 1 3 9 0 2 7 6 0 1 2 3 4 5 6 7 8 9
Performance
Strengths
- With a good time complexity of O(n log n), merge sort is great !!!
- Good to learn Divide and conquer algorithm later used in Dynamic Programming concepts
Weakness
- Poor space complexity of O(n)
- Lots of overhead in copying data between arrays and making new arrays
Fun Fact
Merge Sort is useful for sorting linked lists. Merge Sort is a stable sort which means that the same element in an array maintain their original positions with respect to each other. Overall time complexity of Merge sort is O(nLogn).
Login/Signup to comment
what is p,q,r?
Hey Rahul, we have taken these three variables, to denote the starting and ending point of the two sub arrays