#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;
}