#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 output(int * A, int p, int q)
{
for(int i=p; i<q+1; 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;
//output(A, p, r);
}
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);
//end:
int end;
cin >> end;
return 0;
}
