Merge Sort Algorithm

Merge Sort Algorithm is a sorting algorithm which has time complexity of O(nlog(n)) where n is number of elements in the unsorted list. In merge sort algorithm we divide the array in two halves and then sort those
two sub arrays recursively and after sorting them, the main thing is to merge them so that after merging them we get a sorted array.
Lets understand merge sort with an example :

Fig. 1

In fig. 1 we have an array a[ ] = {2, 6, 4, 5, 3} which is unsorted, so lets apply merge sort on this array to convert it into a sorted one. Follow the steps and observe the figure carefully. We divide the array into 2 sub arrays {2, 6, 4} and {5, 3}. As number of elements in main array are not even so one sub-array must contain one extra element.
Now, first sort a1[ ] = {2, 6, 4} recursively. Divide again a1 into 2 halves {2, 6} and {4}. As set {2, 6} contain 2 elements, so we can divide it further into 2 equal parts i.e. {2} and {6}. Now comes the merging stage because we can't divide the array further.
Merge {2} and {6} in such a way that the new array that formed is sorted. So after merging we should have {2, 6}.
Now merge it again with {4}. We get {2, 4, 6}.
Similarly, after sorting 2nd subarray of main subarray {5, 3} we get {3, 5}.
Merging {2, 4, 6} and {3, 5}, we get {2, 3, 4, 5, 6}.
So finally we can see that we get our sorted array.
Now Lets see the implementation part and don't worry about merging, it is explained in the code itself !

Code for Merge sort in C++ :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

#include<bits/stdc++.h> using namespace std; void merge(int*,int,int,int); void mergeSort(int *a, int lo, int hi){ int mid = (lo + hi) >> 1; if(lo < hi){ mergeSort(a, lo, mid); mergeSort(a, mid + 1, hi); merge(a, lo, mid, hi); } } void merge(int *a, int lo, int mid, int hi){ int i, j; i = lo; j = mid + 1; int newA[hi - lo + 1]; // New array will be our sorted merged array int counter = 0; while(i < mid + 1 && j < hi + 1){ if(a[i] > a[j]){ newA[counter++] = a[j++]; } else{ newA[counter++] = a[i++]; } } while(i < mid + 1){ newA[counter++] = a[i++]; } while(j < hi + 1){ newA[counter++] = a[j++]; } for(i = lo , j = 0; j < counter && i <= hi ; i ++, j ++){ a[i] = newA[j]; } /* leftHalf = {3, 4, 7} , rightHalf = {2, 6} This example is in intermediate stage right now, so left and right halves are already sorted ! newA[] = {} initially int i = 0 is pointer for leftHalf[] int j = 0 is pointer for rightHalf[] *********************************************** if leftHalf[i] < rightHalf[j]: add leftHalf[i] to newA[] and increment i else add rightHalf[j] to newA[] and increment j *********************************************** Clearly 3 > 2 so j = 1 and i = 0 and newA = {2, } 3 < 6, i = 1 and j = 1 and newA = {2, 3, } 4 < 6, i = 2 and j = 1 and newA = {2, 3, 4} ... newA = {2, 3, 4, 6, 7} */ } int main(){ int n; cin >> n; int a[n]; for(int i = 0 ; i < n ; i ++){ cin >> a[i]; } mergeSort(a, 0, n-1); cout << "Sorted Array : \n"; for(int i = 0 ; i < n ; i ++){ cout << a[i] << " "; } cout << "\n"; }

Time Complexity :
Dividing the array : O(log(n))
Merging : O(n)
Overall Complexity : O(n * log(n)) because we are dividing and merging simultaneously !

The End !

Thanks for reading the post buddies !