#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#define NMAX 500001
using namespace std;

ifstream in("algsort.in");
ofstream out("algsort.out");

long long a[NMAX],n;

void ins(int st,int dr)
{
    int j;
    for(int i=st;i<=dr;i++)
    {
        j = i;
        while(j>=st && a[j-1]>a[j])
        {
            swap(a[j-1],a[j]);
            j--;
        }
    }
}

int part(int st,int dr)
{
    int z = rand()%(dr-st+1) + st;
    int z1 = rand()%(dr-st+1) + st;
    int z2 = rand()%(dr-st+1) + st;
    z = (z1+z2+z)/3;
    swap(a[z],a[dr]);
    int x = a[dr];
    int i=st-1;

    for(int j=st;j<dr;j++)
    {
        if(a[j]<=x)
        {
            i++;
            swap(a[i],a[j]);
        }
    }
    swap(a[i+1],a[dr]);

//    for(int i=st;i<dr;i++)
//    {
//        cout << a[i] << " ";
//    }cout << endl;

    return i+1;
}

void quicksort(int st,int dr)
{
    if(dr-st<=9)
        ins(st,dr);
    else
        while(st<dr)
        {
            int mij = part(st,dr);
            quicksort(st,mij-1);
            st = mij+1;

        }
}



int main()
{
    in >> n;
    srand(time(0));
    for(int i=0;i<n;i++)
    {
        in >> a[i];
    }
    quicksort(0,n-1);
    for(int i=0;i<n;i++)
    {
        out << a[i] << " ";
    }
    return 0;
}