#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
typedef int element;
void merge(element *list,element *sorted,int i,int m,int n)
{
int j=m+1,k=i;
while(i<=m && j<=n){
if(list[i]<=list[j])
sorted[k++]=list[i++];
else
sorted[k++]=list[j++];
}
for(;i<=m;i++) sorted[k++]=list[i];
for(;j<=n;j++) sorted[k++]=list[j];
}
void merge_pass(element *list,element *sorted,int n,int length)
{
int i;
for(i=0;i<=n-2*length;i+=2*length)
merge(list,sorted,i,i+length-1,i+2*length-1);
if(i+length<n)
merge(list,sorted,i,i+length-1,n-1);
else
for(;i<n;i++) sorted[i]=list[i];
}
void merge_sort(element* list,int n)
{
int length=1;
element* sorted=new element[n];
while(length<n){
merge_pass(list,sorted,n,length);
length*=2;
merge_pass(sorted,list,n,length);
length*=2;
}
}
int main()
{
int a[]={2,3,4,2,1,2,9,10};
int len=sizeof(a)/sizeof(int);
merge_sort(a,len);
for(int i=0;i<len;i++) cout<<a[i]<<" ";
cout<<endl;
}