#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
void Merge(int A[], int p, int q, int r)
{
    int n1=q-p+1;
    int n2=r-q;     
    int *L=new int[n1+1];
    int *R=new int[n2+1];
    for(int i=0;i<n1;i++)
            L[i]=A[p+i-1];
    for(int j=0;j<n2;j++)
            R[j]=A[q+j];
    L[n1]=100000;
    R[n2]=100000;
    int i=0;
    int j=0;
    for(int k=p-1;k<r;k++)
    {
            if(L[i]<=R[j])
            {
                A[k]=L[i];
                i=i+1;              
            }        
            else
            {
                A[k]=R[j];
                j=j+1;    
            }
    }
    
    
    
}
void MergeSort(int A[], int p, int r)
{
    int q=(p+r)/2; 
   // getchar();
    MergeSort(A,p,q);
    MergeSort(A,p+1,r);
    Merge(A,p,q,r);    
}
int main()
{
   /*const int n=8;
   int A[n]={5,3,6,9,8,7,1,4};
   MergeSort(A,0,7);*/
   const int n=4;
   int A[n]={5,3,6,9};
   MergeSort(A,0,3);
   for(int i=0;i<n;i++)
           cout<<A[i]<<"\t";
   getchar();
   getchar();
   getchar();
   return 0;
}