#include<stdio.h>
#define infile "algsort.in"
#define outfile "algsort.out"
#define nmax 500*1000+1
long v[nmax]; //vectorul in care citim elementele
long n; //retinem numarul de elemente

void citire(long v[nmax], long *n)
	{
	long i;
	scanf("%ld\n",n); //citim numarul de elemente
	for(i=1;i<=*n;scanf("%d",&v[i++])); //citim fiecare element al vectorului in parte
	}

void interclasare(long v[nmax], long p1, long q1, long p2, long q2)
	{
	long w[q1-p1+2]; //in acest vector vom copia primul interval ce trebuie interclasat
	long i,j;
	for(i=p1;i<=q1;i++) w[i-p1+1]=v[i]; //copiem in vector toate elementele primului interval
	j=q1-p1+1;i=1; //in j vom retine numarul total de elemente copiate
	while(i<=j && p2<=q2) //cat timp nu am interclasat toate elementele de le-am copiat
		{
		if(w[i]<v[p2]) v[p1++]=w[i++]; //este mai mic elementul din intervalul copiat....il punem la locul lui
		else v[p1++]=v[p2++]; //este mai mic primul element din multimea necopiata....punem elementul la locul lui
		}
	while(i<=j) v[p1++]=w[i++]; //mai sunt elemente copiate in vector ce trebuie puse la coada
	}

//sorteaza intervalul [p,q]
void msort(long v[nmax], long p, long q)
	{
	if(p<q)
		{
		long m=(p+q)/2; //mijlocul segmenului
		msort(v,p,m); //sortam intervalul [p,m]
		msort(v,m+1,q); //sortam intervalul [m+1,q]
		interclasare(v,p,m,m+1,q); //interclasam cele 2 intervale sortate [p,m] cu [m+1,q]
		}
	}

void afisare(long v[nmax], long n)
	{
	long i;
	for(i=1;i<=n;i++) //trecem pe la fiecare element al vectorului
		printf("%d ",v[i]); //il afisem
	}

int main()
{
//deschidem fisiere
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(v,&n); //citim
msort(v,1,n); //sortam
afisare(v,n); //afisem

//inchidem fisiere
fclose(stdin);
fclose(stdout);
return 0;
}