Merge Sort

merge_sort.cpp

#include <bits/stdc++.h>
using namespace std;
void mergesort(int [],int,int);
void merge(int[],int,int,int);

int main()
{
    int a[30],p,r,q,n;
    cout<<"enter the number of element";
    cin>>n;
    cout<<"element :";
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    // Call of initial function
    mergesort(a,0,n-1);
    cout<<"\n Array after sorting";
    for(int i=0; i<n; i++)
    {
        cout << " -> "<<a[i];
    }
    return 0;
}
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[i];
        k++;
        j++;
    }
    // Assign sorted data stored in temp[] to a[].
	for (i = low; i <= high; i++)
	{
		a[i] = temp[i-low];
	}
}
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);
    }
}