C++ Programming Code Examples C++ > Sorting Searching Code Examples C++ Program to Implement Merge Sort C++ Program to Implement Merge Sort - Merge-sort is based on an algorithmic design pattern called divide-and-conquer. - It forms tree structure. - The height of the tree will be log(n). - we merge n element at every level of the tree. - The time complexity of this algorithm is O(n*log(n)). - Split the data into two equal half until we get at most one element in both half. - Merge Both into one making sure the resulting sequence is sorted. - Recursively split them and merge on the basis of constraint given in step 1. - Display the result. - Exit. #include <iostream> using namespace std; // A function to merge the two half into a sorted data. void Merge(int *a, int low, int high, int mid) { // We have low to mid and mid+1 to high already sorted. int i, j, k, temp[high-low+1]; i = low; k = 0; j = mid + 1; // Merge the two parts into temp[]. while (i <= mid && j <= high) { if (a[i] < a[j]) { temp[k] = a[i]; k++; i++; } else { temp[k] = a[j]; k++; j++; } } // Insert all the remaining values from i to mid into temp[]. while (i <= mid) { temp[k] = a[i]; k++; i++; } // Insert all the remaining values from j to high into temp[]. while (j <= high) { temp[k] = a[j]; k++; j++; } // Assign sorted data stored in temp[] to a[]. for (i = low; i <= high; i++) { a[i] = temp[i-low]; } } // A function to split array into two parts. void MergeSort(int *a, int low, int high) { int mid; if (low < high) { mid=(low+high)/2; // Split the data into two half. MergeSort(a, low, mid); MergeSort(a, mid+1, high); // Merge them to get sorted output. Merge(a, low, high, mid); } } int main() { int n, i; cout<<"\nEnter the number of data element to be sorted: "; cin>>n; int arr[n]; for(i = 0; i < n; i++) { cout<<"Enter element "<<i+1<<": "; cin>>arr[i]; } MergeSort(arr, 0, n-1); // Printing the sorted data. cout<<"\nSorted Data "; for (i = 0; i < n; i++) cout<<"->"<<arr[i]; return 0; }