Program to Implement Merge Sort
#include <iostream> using namespace std; void Merge(int *arr, int first, int last, int mid) { int i, j, k, temparr[first-last+1]; i = first; k = 0; j = mid + 1; // Merge into temparr[]. while (i <= mid && j <= last) { if (arr[i] < arr[j]) { temparr[k] = arr[i]; k++; i++; } else { temparr[k] = arr[j]; k++; j++; } } // Insert remaining values from i to mid into temparr[]. while (i <= mid) { temparr[k] = arr[i]; k++; i++; } // Insert remaining values from j to high into temparr[]. while (j <= last) { temparr[k] = arr[j]; k++; j++; } // Assigning sorted data from temprr[] to arr[]. for (i = first; i <= last; i++) { arr[i] = temparr[i-first]; } } // spliting array into two parts. void MergeSort(int *a, int first, int last) { int mid; if (first < last) { mid=(first+last)/2; // Spliting the data into two half. MergeSort(a, first, mid); MergeSort(a, mid+1, last); // Merging elements to get sorted output. Merge(a, first, last, mid); } } int main() { int num, i; cout<<"\nHow many number of elements do want to sort: "; cin>>num; int arr[num]; for(i = 0; i < num; i++) { cout<<"Enter the element "<<i+1<<": "; cin>>arr[i]; } MergeSort(arr, 0, num-1); // Printing the sorted data. cout<<"\n Sorted Elements after merge sort are "; for (i = 0; i < num; i++) cout<<"->"<<arr[i]; return 0; }
Output:-