#include <iostream>
using namespace std;

void Merge(int a1[],int low,int mid,int high,int a2[])
{
    int i=low,k=low,j=mid+1;
   
    while((i<=mid)&&(j<=high))
    {
        if(a1[i]<=a1[j])
            a2[k++]=a1[i++];
        else
            a2[k++]=a1[j++];
    }
    while(i<=mid)
        a2[k++]=a1[i++];
    while(j<high)
        a2[k++]=a1[j++];
}

void merge_sort(int a[],int low,int high,int b[])
{
    int *t=new int[high-low+1]();
    if(low==high)
        b[low]=a[low];
    else
    {
        int mid=(low+high)/2;
        merge_sort(a,low,mid,t);
        merge_sort(a,mid+1,high,t);
        Merge(t,low,mid,high,b);
    }
    delete []t;
}

int main()
{
    int a[]={70,30,40,10,80,20,90,100,75,60,45};
    int length=sizeof(a)/sizeof(int);
    int b[length];
  
    merge_sort(a,0,length-1,b);
    for(int i=0;i<length;++i)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}