#include<fstream>
#include<ctime>
#include<cstdlib>
#define numaru 500001
using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");
int v[numaru],n;
void sort2(int p,int q)
{
    int i,x,j;
    for(i=p+1;i<=q;++i)
    {
        for(x=v[i],j=i-1;x<v[j] && j>p-1;v[j+1]=v[j],--j);
        v[j+1]=x;
    }
}
void sortsort(int p,int q)
{
    if(p<q)
    {
        if(q-p+1>=11)sort2(p,q);
        else
        {
            int i=p,j=q,k=rand()%(p-q)+p+1,x=v[k];
            while(i<j)
            {
                while( v[i]<x )++i;
                while( v[j]>x )--j;
                if(v[i]==v[j])++i;
                else if(i<j) v[i]=(v[i]+v[j])-(v[j]=v[i]);
            }
            sortsort(p,j-1);
            sortsort(j+1,q);
        }
    }
}
int main()
{
    f>>n; for(int i=1;i<=n;++i)f>>v[i];
    sortsort(1,n);
    for(int i=1;i<=n;g<<v[i]<<" ",++i);
    f.close();
    g.close();
    return 0;
}