# Merge Sort Algorithm (with Example) with C++ Code | Sorting Algorithms | Data Structures & Algorithms

> Merge Sort Algorithm is a

There are 3 Phases (4 major steps) in the Merge Sort Algorithm –

**Divide & Conquer**algorithm. It divides input array in two halves, calls itself for the two halves(recursively) and then merges the two sorted halves. A separate**merge()**function is used for merging two halves. Merge sort is one of the most efficient sorting algorithms.**>> Time Complexity: O(nlog(n))**

**Working –**

There are 3 Phases (4 major steps) in the Merge Sort Algorithm –- Division Phase – Divide the array(list) into 2 halves by finding the midpoint of the array(list).
- Midpoint (m) = (left + right)/ 2
*Here left is the starting index & right is the last index of the array(list)*

- Recursion Phase –
- Call Merge Sort on the left sub-array (sub-list)
- Call Merge Sort on the right sub-array (sub-list)

- Merge Phase –
- Call merge function to merge the divided sub-arrays back to the original array.
- Perform sorting of these smaller sub arrays before merging them back.

**Merge Sort Algorithm(Pseudo Code) –**

1 2 3 4 5 6 7 8 9 10 | mergeSort(arr[],l,r) //arr is array, l is left, r is right { if(l<r) { midpoint = (l+r)/2 mergeSort(arr,l,m) mergeSort(arr,m+1,r) merge(arr,l,m,r) } } |

**C++ Program to Implement Merge Sort –**

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 75 76 77 78 79 80 81 82 83 84 85 | # include < iostream > using namespace std; void merge(int arr[], int l, int m, int r) { int i = l; int j = m + 1; int k = l; /* create temp array */ int temp[5]; while (i <= m && j <= r) { if (arr[i] <= arr[j]) { temp[k] = arr[i]; i++; k++; } else { temp[k] = arr[j]; j++; k++; } } /* Copy the remaining elements of first half, if there are any */ while (i <= m) { temp[k] = arr[i]; i++; k++; } /* Copy the remaining elements of second half, if there are any */ while (j <= r) { temp[k] = arr[j]; j++; k++; } /* Copy the temp array to original array */ for (int p = l; p <= r; p++) { arr[p] = temp[p]; } } /* l is for left index and r is right index of the sub-array of arr to be sorted */ void mergeSort(int arr[], int l, int r) { if (l < r) { // find midpoint int m = (l + r) / 2; // recurcive mergesort first and second halves mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // merge merge(arr, l, m, r); } } int main() { int myarray[5]; //int arr_size = sizeof(myarray)/sizeof(myarray[0]); int arr_size = 5; cout << "Enter 5 integers in any order: " << endl; for (int i = 0; i < 5; i++) { cin >> myarray[i]; } cout << "Before Sorting" << endl; for (int i = 0; i < 5; i++) { cout << myarray[i] << " "; } cout << endl; mergeSort(myarray, 0, (arr_size - 1)); // mergesort(arr,left,right) called cout << "After Sorting" << endl; for (int i = 0; i < 5; i++) { cout << myarray[i] << " "; } return 0; } |