//Merge Sort using Divide and conquer
#include<cstdio>
#include<iostream>
int a[100];
using namespace std;
void merge_sort(int a[],int low,int mid,int high)
{
int i=low,h=low,j=mid+1;
int b[100];
while(h<=mid && j<=high)
{
if(a[h]<=a[j])
b[i++]=a[h++];
else
b[i++]=a[j++];
}
if(h>mid)
{
for(int k=j;k<=high;k++)
b[i++]=a[k];
}
else
for(int k=h;k<=mid;k++)
b[i++]=a[k];
for(int i=low;i<=high;i++)
{
a[i]=b[i];
//cout<<a[i]<<" ";
}
//cout<<endl;
}
void merge(int a[],int l,int h)
{
if(l<h)
{
int mid=(l+h)/2;
merge(a,l,mid);
merge(a,mid+1,h);
merge_sort(a,l,mid,h);
}
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
merge(a,1,n);
printf("****Merge Sort****\n");
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
Ly9NZXJnZSBTb3J0IHVzaW5nIERpdmlkZSBhbmQgY29ucXVlciAKI2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxpb3N0cmVhbT4KaW50IGFbMTAwXTsKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdm9pZCBtZXJnZV9zb3J0KGludCBhW10saW50IGxvdyxpbnQgbWlkLGludCBoaWdoKQp7CglpbnQgaT1sb3csaD1sb3csaj1taWQrMTsKCWludCBiWzEwMF07Cgl3aGlsZShoPD1taWQgJiYgajw9aGlnaCkKCXsKCQlpZihhW2hdPD1hW2pdKQoJCWJbaSsrXT1hW2grK107CgkJZWxzZQoJCWJbaSsrXT1hW2orK107Cgl9CglpZihoPm1pZCkKCXsKCQlmb3IoaW50IGs9ajtrPD1oaWdoO2srKykKCQliW2krK109YVtrXTsKCX0KCWVsc2UKCQlmb3IoaW50IGs9aDtrPD1taWQ7aysrKQoJCWJbaSsrXT1hW2tdOwoJZm9yKGludCBpPWxvdztpPD1oaWdoO2krKykKCXsKCQlhW2ldPWJbaV07CgkJLy9jb3V0PDxhW2ldPDwiICI7Cgl9CQoJLy9jb3V0PDxlbmRsOwp9CnZvaWQgbWVyZ2UoaW50IGFbXSxpbnQgbCxpbnQgaCkKewoJaWYobDxoKQoJewoJCWludCBtaWQ9KGwraCkvMjsKCQltZXJnZShhLGwsbWlkKTsKCQltZXJnZShhLG1pZCsxLGgpOwoJCW1lcmdlX3NvcnQoYSxsLG1pZCxoKTsKCX0KfQppbnQgbWFpbigpCnsKCWludCBuOwoJY2luPj5uOwoJZm9yKGludCBpPTE7aTw9bjtpKyspCgljaW4+PmFbaV07CgltZXJnZShhLDEsbik7CglwcmludGYoIioqKipNZXJnZSBTb3J0KioqKlxuIik7Cglmb3IoaW50IGk9MTtpPD1uO2krKykKCWNvdXQ8PGFbaV08PCIgIjsKCWNvdXQ8PGVuZGw7Cn0=