#include<stdio.h>
#define Nmax 500001
int N,v[Nmax];
void read_data()
{
	FILE*f = fopen("algsort.in","r");
	fscanf(f,"%d",&N);
	for(int i=1;i<=N;++i)
		fscanf(f,"%d",&v[i]);
	fclose(f);
}
void show(int v[])
{
	int i;
	printf("\n");
	for(i=1;i<=N;++i)
	{
		printf("%d ",v[i]);
	}
	printf("\n\n");
}
void inter(int left, int right, int mid)
{
	//printf("%d %d %d\n",left,right,mid);

	int c[Nmax],i,j,cnt=0;
	for(i=left,j=mid+1;i<=mid && j<=right;)
	{
		
		if(v[i] <= v[j])
		{
			c[++cnt] = v[i];
			++i;
		}
		else
		{
			c[++cnt] = v[j];
			++j;
		}
	}
	if(i<=mid)
	{
		for(;i<=mid;++i)
			c[++cnt] = v[i];
	}
	if(j<=right)
	{
		for(;j<=right;++j)
			c[++cnt] = v[j];
	}

	for(i=left,j=0;i<=right;++i)
	{
		v[i] = c[++j];
	}
}
void merge(int left,int right)
{
	if(left >= right)
		return;
	int mid = (left+right)/2;
	merge(left,mid);
	merge(mid+1,right);


	inter(left,right,mid);
}

void show_data()
{
	FILE*g = fopen("algsort.out","w");
	for(int i=1;i<=N;++i)
	{
		fprintf(g,"%d ",v[i]);
	}
	fclose(g);
}
int main()
{
	read_data();
	merge(1,N);
	show_data();
	return 0;
}