#include<stdio.h>
#include<stdlib.h>
#include<ctime>
int v[500001],n;

void citire()
{
	FILE*f=fopen("algsort.in","r");
	fscanf(f,"%d",&n);
	for(int i=0;i<n;i++)
		fscanf(f,"%d",&v[i]);
	fclose(f);
}

void scriere()
{
	FILE*f=fopen("algsort.out","w");
	for(int i=0;i<n;i++) fprintf(f,"%d ",v[i]);
	fclose(f);
}

int Partitie(int A[],int st, int dr)
{
	int poz=st+ rand()%(dr-st+1);
	int tmp=A[poz];
	A[poz]=A[st];
	A[st]=tmp;
	
	int V=A[st];
	--st; ++dr;
	while(st<dr)
	{
		do
			--dr;
		while( st<dr && A[dr]>V);
		do
			++st;
		while(st<dr && A[st]<V);
		if(st<dr)
		{
			tmp=A[st];
			A[st]=A[dr];
			A[dr]=tmp;
		}
	}
	return dr;
}

void qSort(int A[],int st,int dr)
{
	while(st<dr)
	{
		int P=Partitie(A,st,dr);
		if(P-st<dr-P-1)
		{
			qSort(A,st,P);
			st=P+1;
		}
		else 
		{
			qSort(A,P+1,dr);
			dr=P;
		}
	}
}



int main()
{
	citire();
	srand((unsigned)time(0));
	qSort(v,0,n-1);
	scriere();
	return 0;
}