#include <stdio.h>  
#include <stdlib.h>  
  
void merge(int starts,int startd,int stopd,int *a){  
int n=stopd-starts+1;  
int is=starts,id=startd,stops=startd-1,it=0,i;  
int *temp=(int*)malloc(n*sizeof(int));  
   
while(is<=stops && id<=stopd)  
    if (a[is]<a[id])  
        temp[it++]=a[is++];  
    else  
        temp[it++]=a[id++];  
   
while (is<=stops)  
     temp[it++]=a[is++];  
while (id<=stopd)  
    temp[it++]=a[id++];  
   
for (i=0;i<n;i++)  
    a[starts+i]=temp[i];  
free(temp);  
}  
   
void MS(int s,int d,int *a){  
if (s<d)  
    {  
    int m=(s+d)/2;  
    MS(s,m,a);  
    MS(m+1,d,a);  
    merge(s,m+1,d,a);  
    }  
}  
  
void MergeSort(int n,int *a){  
    MS(0,n-1,a);  
}  
   
   
int main(){  
int n,j;  
FILE *in,*out;  
in=fopen("algsort.in","rt");  
out=fopen("algsort.out","wt");  
fscanf(in,"%d",&n);  
int *v=(int*)malloc(n*sizeof(int));  
for (j=0;j<n;++j)  
    fscanf(in,"%d ",&v[j]);  
MergeSort(n,v);  
for (j=0;j<n;++j)  
    fprintf(out,"%d ",v[j]);  
fclose(in);  
fclose(out);  
return 0;  
}