This is a C++ program to sort the given data using Merge Sort.

1. Merge-sort is based on an algorithmic design pattern called divide-and-conquer.

2. It forms tree structure.

3. The height of the tree will be log(n).

4. we merge n element at every level of the tree.

5. The time complexity of this algorithm is O(n*log(n)).

1. Split the data into two equal half until we get at most one element in both half.

2. Merge Both into one making sure the resulting sequence is sorted.

3. Recursively split them and merge on the basis of constraint given in step 1.

4. Display the result.

5. Exit.

C++ program to implement Merge sort.

This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#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; }

1. Take input of data.

2. Call MergeSort() function.

3. Recursively split the array into two equal parts.

4. Split them until we get at most one element in both half.

5. Combine the result by invoking Merge().

6. It combines the individually sorted data from low to mid and mid+1 to high.

7. Return to main and display the result.

8. Exit.

Case 1: Enter the number of data element to be sorted: 10 Enter element 1: 23 Enter element 2: 987 Enter element 3: 45 Enter element 4: 65 Enter element 5: 32 Enter element 6: 9 Enter element 7: 475 Enter element 8: 1 Enter element 9: 17 Enter element 10: 3 Sorted Data ->1->3->9->17->23->32->45->65->475->987

**Sanfoundry Global Education & Learning Series – C++ Algorithms.**

To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.