# C++ Program to Implement Merge Sort

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

## Problem Description

1. Merge-sort is based on an algorithmic design pattern called divide-and-conquer.
2. It forms a 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)).

## Problem Solution

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.Program/Source Code

C++ program to implement Merge sort.
This program is successfully run on Dev-C++ using the 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;
}```

## Program Explanation

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.