#include <fstream>
#include <stdlib.h>
#include <time.h>
#define nmax 500002
using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");
int v[nmax],n;
void interschimba(int i,int j)
{
    int aux=v[i];
    v[i]=v[j];
    v[j]=aux;
}
void QuickSort(int st,int dr)
{
    if(st>=dr) return;
    int x1=st+rand()%(dr-st+1);
    int x2=st+rand()%(dr-st+1);
    int x3=st+rand()%(dr-st+1);
    int pivot,punct_partitie;
    if((v[x1]<=v[x2] && v[x2]<=v[x3])||(v[x3]<=v[x2] && v[x2]<=v[x1]))
        pivot=v[x2];
    else if((v[x1]<=v[x3] && v[x3]<=v[x2]) || (v[x2]<=v[x3] && v[x3]<=v[x1]))
        pivot=v[x3];
    else pivot=v[x1];
    int i=st-1,j=dr+1;
    while(i<j)
    {
        while(v[++i]<pivot);
        while(v[--j]>pivot);
        if(i>=j)
            punct_partitie=j;
        else
            interschimba(i,j);
    }
    QuickSort(st,punct_partitie);
    QuickSort(punct_partitie+1,dr);
}
int main()
{
    srand(time(NULL));
    f>>n;
    for(int i=1; i<=n; ++i)
        f>>v[i];
    QuickSort(1,n);
    for(int i=1;i<=n;++i)
        g<<v[i]<<' ';
    return 0;
}