/// Merge Sort
#include<iostream>
using namespace std;

void merge(int a[],int L[],int lcount,int R[],int rcount)
{
    int i=0,j=0,k=0;
    while(i<lcount && j<rcount)
    {
        if(L[i]<R[j]) a[k++]=L[i++];
        else a[k++]=R[j++];
    }
    
    
    while(i<lcount) a[k++]=L[i++];
    while(j<rcount) a[k++]=R[j++];


}

void mergeSort(int a[],int n)
{
    int L[n],R[n],mid,i,j,k;
    if(n<2) return;
    mid=n/2;
    L[mid];
    R[n-mid];

    for(i=0; i<mid; i++) L[i]=a[i];
    for(i=mid; i<n; i++) R[i-mid]=a[i];

    mergeSort(L,mid);
    mergeSort(R,n-mid);

    merge(a,L,mid,R,n-mid);


}


int main()
{
    int i,a[]= {3,6,2,9,1,4,7,5};
    int n;
    n=sizeof(a)/sizeof(a[0]);
    mergeSort(a,n);

    for(i=0; i<n; i++) cout<<a[i]<<" ";

    return 0;
}