#include<fstream>
using namespace std;
int a[510000];
ofstream g("algsort.out");
void interclasare(int start1,int fin1, int fin2)//start2 coincide cu fin1+1
{int aux[510000],i=start1,j=fin1+1,k=0,k1;
//urmeaza interclasarea clasica
while(i<=fin1 && j<=fin2){
						if(a[i]<=a[j])aux[++k]=a[i++];
						else aux[++k]=a[j++];
							}
while(j<=fin2)aux[++k]=a[j++];
while(i<=fin1)aux[++k]=a[i++];//s-a terminat interclasarea clasica
k1=start1;// se sorteaza el in vectorul "mare"incepand cu pozitia de care avem nevoie
for(i=1;i<=fin2-start1+1;i++)
	a[k1++]=aux[i];
}
void recursie(int stanga, int dreapta)
{if(stanga<dreapta)
{int mijloc=(stanga+dreapta)/2;//initializare mijloc
recursie(stanga,mijloc);//e apelata funcita recursiv pt a o sparge in bucati mai mici a.i. sa fie 
recursie(mijloc+1,dreapta);// interclasati vectorii minimi intai si apoi cei mai mari
interclasare(stanga,mijloc,dreapta);}
}
int main()
{int n,i;
ifstream f("algsort.in");
f>>n;
for(i=1;i<=n;i++)
	f>>a[i];
recursie(1,n);
for(i=1;i<=n;i++)g<<a[i]<<" ";
}