#include  <iostream>
using namespace std;
#include <assert.h>
int MergeSort(int A[],int p,int q,int r)
{
    int n1 = q-p+2;
    int n2 = r-q+1;
    int *parray1 = new int[n1];
    int *parray2 = new int[n2];
    assert(parray1);
    assert(parray2);
    for(int i = 0;i<n1-1;i++)
    {
        parray1[i] = A[p+i];
    }
    parray1[n1-1] = 0xffff;
    for(int i = 0;i<n2-1;i++)
    {
        parray2[i] = A[q+i+1];
    }
    parray2[n2-1] = 0xffff;
    for(int i=0,j=0,k=p;k<=r;k++)
    {
        if(parray1[i]>parray2[j])
        {
            A[k] = parray2[j];
            j++;
        }
        else
        {
            A[k] = parray1[i];
            i++;
        }
    }

    delete []parray1;
    delete []parray2;


}
int Merge(int A[],int p,int r)
{
    if(p<r)
    {
       int q = (p+r)/2;
       Merge(A,p,q);
       Merge(A,q+1,r);
       MergeSort(A,p,q,r);
    }
}
int main()
{
    int a[]={5,2,4,7,1,3,2,6};
    Merge(a,0,sizeof(a)/sizeof(int)-1);
    for(int i=0;i<8;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}