#include<iostream>
using namespace std;
void merge(int a[],int left,int mid, int right)
{
int k=left;
int i=0,j=0;
int b[right-left+1];
for(i=left;i<=right;i++)
b[i]=a[i];
for(i=left,j=mid+1;i<=mid&&j<=right;)
{
if(b[i]<b[j])
{
a[k++]=b[i++];
}else{
a[k++]=b[j++];
}
}
while(i<=mid) a[k++]=b[i++];
while(j<=right) a[k++]=b[j++];
}
void mergeSort(int a[],int left,int right)
{
if(left < right)
{
int mid = (left+right)/2;
mergeSort(a,left,mid);
mergeSort(a,mid+1,right);
merge(a,left,mid,right);
}
}
int main()
{
int a[10]={5,2,1,7,9,0,3,4,8,6};
mergeSort(a,0,9);
for(int i=0;i<10;i++)
cout<<a[i]<<" ";
cout<<endl;
}
