#include <fstream>
#include <ctime>
#include <stdlib.h>
using namespace std;

int v[500010], n, i, j, aux;

/// functia poz are timp de executare de ordin n intucat la fiecare pas al lui while i si j se apropie cu o unitate
/// daca sirul esre sortat deja (crescator sau descrescator) poz va da mereu o extremitate
/// a secventei st,dr si atunci unul dintre cele doua autoapeluri
/// se face intr-o secventa vida dar celalalt in una doar cu 1 mai scurta decat cea de la pasul anterior deci de n ori se va face poz cu n pasi si se ajunge la timp de executare patratic

/// ne-a avantaja daca sirul dat ar fi asa incat elementul de fixat in poz s-ar duce cat mai ja mijloc, astfel injumatatindu-se mereu lungimea secventei pe care merge poz
/// putem obtine asta daca la inceput amestecam bine sirul (daca sirul dat este random, cu cat este mai lung cu atat este mai probabil ca elementul de fixat - pe care il mai numim si pivot - sa  mearga sppre mijloc)

int poz(int st, int dr) {
    int i = st, j = dr, ii = 0, jj = -1;
    while (i!=j) {
        if (v[i] > v[j]) {
            int aux = v[i];
            v[i] = v[j];
            v[j] = aux;
            aux = ii;
            ii = -jj;
            jj = -aux;
        }
        i+=ii;
        j+=jj;
    }
    return i;

}

void sorteaza(int st, int dr) {
    if (st < dr) {
        int p = poz(st, dr);
        /// duce pe v[st] la locul sau in cadrul secventei
        /// si inainte sa returneze pozitia unde l-a dus
        /// separa celelalte elemente ale secvente astfel:
        /// cele mai mici ca elementul asezat in tanga lui si cele mai mari in dreapta
        sorteaza(st, p-1);
        sorteaza(p+1, dr);
        /// observam ca la acest algoritm operatiile se fac inainte de autoapeluri
        /// aitoapelurile avand sens tocmai datorita separarii elementelor
    }
}

int main() {
    ifstream fin ("algsort.in");
    ofstream fout("algsort.out");
    fin >> n;
    for (i=1;i<=n;i++)
        fin>>v[i];
    srand(time(0));
    for (i=n;i>=3;i--) {
        j = 1 + rand() % (i-1);
        aux = v[i];
        v[i] = v[j];
        v[j] = aux;
    }
    sorteaza(1, n);
    for (i=1;i<=n;i++)
        fout<<v[i]<<" ";

}