#include<iostream>
using namespace std;
void merge(int a[],int low,int mid,int high);
void mergesort(int a[],int low, int high)
{
	if(high>low){
		int mid=(low+high)/2;
		mergesort(a,low,mid);
		mergesort(a,(mid+1),high);
		merge(a,low,mid,high);
	}
}
 
void merge(int a[],int low,int mid,int high){
 
	int t[(high-low)+1];
	int il=0;
	int ir=0;
	int nl = mid - low + 1;
	int nr = high - mid;
	while((il<nl)&&(ir<nr)){
		if(a[low+il]<=a[mid+1+ir]){
			t[il+ir]=a[low+il];
			il++;
		}
		else{
			t[il+ir]=a[mid+1+ir];
			ir++;
		}
	}	
	while(il<nl){
			t[il+ir]=a[low+il];
			il++;
	}
	while(ir<nr){
			t[il+ir]=a[mid+1+ir];
			ir++;
	}
	for(int i=low;i<high;i++){
		a[i]=t[i-low];
	}
 
}
 
 
int main()
{
	int a[10] = {0,4,9,11,16,2,3,5,7,8};
	mergesort(a,0,10);
	for(int i=0;i<10;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}