Merge Sort Algorithm (with Example) with C++ Code | Sorting Algorithms | Data Structures & Algorithms
> Merge Sort Algorithm is a 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) –
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(with fixed size of array) –
#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; }
C++ Program to Implement Merge Sort(with dynamic size of array) –
#include <iostream> using namespace std; void merge(int arr[], int l, int m, int r, int size) { int i = l; int j = m + 1; int k = l; /* create temp array */ int temp[size]; 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, int size) { if (l < r) { // find midpoint int m = (l + r) / 2; /* recurcive mergesort first and second halves */ mergeSort(arr, l, m, size); mergeSort(arr, m + 1, r, size); // merge merge(arr, l, m, r, size); } } int main() { cout << "Enter size of array: " << endl; int size; cin >> size; int myarray[size]; cout << "Enter " << size << " integers in any order: " << endl; for (int i = 0; i < size; i++) { cin >> myarray[i]; } cout << "Before Sorting" << endl; for (int i = 0; i < size; i++) { cout << myarray[i] << " "; } cout << endl; mergeSort(myarray, 0, (size - 1), size); // mergesort(arr,left,right) called cout << "After Sorting" << endl; for (int i = 0; i < size; i++) { cout << myarray[i] << " "; } return 0; }