# include<stdio.h>
# include<iostream.h>
# include<conio.h>
#define max 5000
void MergeSort(int low, int high);
void Merge(int low, int mid , int high);
int a[max];
int b[max];
int main(void)
{
int i,n,high,low;
cout<<"How many element:";
cin>>n;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
high=n;
low=0;
for(i=1;i<=n;i++)
{
MergeSort(low,high);
cout<<a[i]<<"\t";
}
getch();
return 0;
}
void MergeSort(int low, int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
MergeSort(low, mid);
MergeSort(mid+1,high);
Merge(low, mid, high);
}
}
void Merge(int low, int mid, int high)
{
int h,i,j,k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h=h+1;
}
else
{
b[i]=a[j];
j=j+1;
}
i=i+1;
}
if(h>mid)
{
for(k=j; k<=high; k++)
{
b[i]=a[k];
i=i+1;
}
}
else
{
for(k=h; k<=mid; k++)
{
b[i]=a[k];
i=i+1;
}
}
for(k=low; k<=high; k++)
a[k]=b[k];
}
