#include <iostream>
#include <string>
using namespace std;

void Merge(int * A, int p, int q, int r);

void output(int * A, int size)
{
??? for(int i=0; i<size; i++)
??? ??? cout << A[i] << " ";
???
??? cout << endl;
}

void MergeSort(int * A, int p, int r) //sort A[p,r]
{
??? if(p < r)
??? {
??? ??? int q = (p+r)/2;
??? ??? MergeSort(A, p, q);
??? ??? MergeSort(A, q+1, r);
??? ??? Merge(A, p, q, r);
??? }
}

void Merge(int * A, int p, int q, int r) //merge A[p,q] with A[q+1,r]
{
??? // array1 A[p,q]
??? // array2 A[q+1,r]
??? int * pp = new int[r-p+1];
??? int i1=p;
??? int i2=q+1;
??? for(int i=0; i<r-p+1; i++)
??? {
??? ??? if(i1<=q && i2<=r)
??? ??? {
??? ??? ??? if(A[i1]<A[i2])
??? ??? ??? {
??? ??? ??? ??? pp[i] = A[i1];
??? ??? ??? ??? i1++;
??? ??? ??? }
??? ??? ??? else
??? ??? ??? {
??? ??? ??? ??? pp[i] = A[i2];
??? ??? ??? ??? i2++;
??? ??? ??? }
??? ??? }
??? ??? else if(i1>q)
??? ??? {
??? ??? ??? for(;i<r-p+1;i++)
??? ??? ??? {
??? ??? ??? ??? pp[i] = A[i2];
??? ??? ??? ??? i2++;
??? ??? ??? }
??? ??? ???
??? ??? ??? break;
??? ??? }
??? ??? else if(i2>r)
??? ??? {
??? ??? ??? for(;i<r-p+1;i++)
??? ??? ??? {
??? ??? ??? ??? pp[i] = A[i1];
??? ??? ??? ??? i1++;
??? ??? ??? }
??? ??? ???
??? ??? ??? break;
??? ??? }
??? }
???
??? for(int i=p; i<=r; i++)
??? {
??? ??? int t = pp[i-p];
??? ??? A[i] = pp[i-p];
??? }
???
??? delete [] pp;
}


int main()
{
??? int Ar[] = {11,2,9,7,6,5,3,8,2,3,5,1,-5,8,7};???
??? int size = sizeof(Ar)/sizeof(int);
??? output(Ar, size);
???
??? MergeSort(Ar,0,size-1);???
??? output(Ar, size);???

??? return 0;
}