// quicksort fara pivot aleator(n log n pe cazul mediu si pe
// majoritatea cazurilor), o(n^2) pe cazul oarecare

#include <fstream>
#include <stdlib.h>
#include <time.h>

using namespace std;

int n, i, x, p;
int v[500010];

int pozitioneaza(int st, int dr) {
    int pi = 0;
    int pj = -1;
    int aux;

    int p = 1 + rand()%(dr-st);
    aux = v[st];
    v[st] = v[p + st];
    v[p + st] = aux;

    while (st != dr) {
        if (v[st] > v[dr]) {
            aux = v[st];
            v[st] = v[dr];
            v[dr] = aux;
            aux = pi;
            pi = -pj;
            pj = -aux;
        }
        st += pi;
        dr += pj;
    }
    return st;
}

void sorteaza(int st, int dr) {
    if (st < dr) {
        int p = pozitioneaza(st, dr); // duce la locul lui pe v[st]
                            // si ce e in stg e mai mic
                            // si ce e in dreapta e mai mare
        sorteaza(st, p-1);
        sorteaza(p+1, dr);
    }
}

int main () {

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

    fin>>n;
    // numaram de cate ori apare fiecare valoare
    for (i=1;i<=n;i++) {
        fin>>v[i];
    }

    srand(time(0));
    /*
    for (i=n;i>=2;i--) {
        p = 1 + rand() % (i-1);
        int aux = v[i];
        v[i] = v[p];
        v[p] = aux;

    }
    */

    sorteaza(1, n);

    for (i=1;i<=n;i++)
        fout<<v[i]<<" ";

    return 0;
}