#include <stdio.h>
#include <algorithm>
#define NMax 500010
using namespace std;

const char IN[]="algsort.in",OUT[]="algsort.out";

int N;
int v[NMax];

void slowsort(int ls,int ld){
	for (int i=ls;i<=ld;++i)
		for (int j=i;j>ls && v[j]<v[j-1];--j)
			swap(v[j],v[j-1]);
}

int getpivot(int ls,int ld){

	int i,j,y;

	while (ls<ld){

		for (i=j=ls;i<=ld;i+=5)
		{
			y=min(ld,i+4);
			slowsort(i,y);
			swap(v[j++],v[i+((y-i+1)>>1) + ((y-i+1)&1)-1]);
		}
		ld=j-1;
	}
}

void sort(int ls,int ld){

	if (ls>=ld) return;
	if (ld-ls<5){
		slowsort(ls,ld);
		return;
	}
	int i,j;bool isSorted=true;
	getpivot(ls,ld);
	for (i=ls+1,j=ls;i<=ld;++i)
	{
		isSorted&= v[i-1]<=v[i];
		if (v[i]<v[ls])
			swap(v[++j],v[i]);
	}
	if (isSorted) return;
	swap(v[j],v[ls]);
	sort(ls,j-1);
	sort(j+1,ld);
}

int main()
{
	int i;
	freopen(IN,"r",stdin);
	scanf("%d",&N);
	for (i=1;i<=N;++i) scanf("%d",v+i);
	fclose(stdin);

	sort(1,N);

	freopen(OUT,"w",stdout);
	for (i=1;i<=N;++i) printf("%d ",v[i]);
	fclose(stdout);
	return 0;
}