#include
using namespace std;
void merge(int a[],int spos,int epos)
{
int mid=(spos+epos)/2;
int temp[10];
int tempp[10];
for(int i=0;i<=mid;i++)
{temp[i]=a[i];}
for(int i=mid+1;i<epos;i++)
{tempp[i-mid-1]=a[i];}
int k=0;int i=0;int j=0;
while(i<=mid && j<=epos-mid-1)
{if (temp[i]>tempp[j])
{
a[k]=tempp[j];
k++;j++;}
else
{
a[k]=temp[i];
k++;
i++;
}}
while(i<=mid)
{a[k]=temp[i];
k++;i++;
}
while(j<=epos-mid-1)
{a[k]=tempp[j];
k++;j++;}
}
void mergesort(int a[],int spos,int epos)
{
if (spos>=epos) return;
int mid=(spos+epos)/2;
mergesort(a,0,mid);
mergesort(a,mid+1,epos);
merge(a,spos,epos);
}
int main()
{
int a[]={1,4,6,9,3,5,7,2,8,0};
int n=10;
mergesort(a,0,n-1);
for (int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl;
}