#include <fstream>
using namespace std;

const int N = 5e5;
const int Size = 8, Mask = (1 << Size) - 1;

int v[N], pos[1 + Mask], n;

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

void selSort(int st, int dr){
    for (int i = st ; i < dr ; i++)
        for (int j = i + 1 ; j <= dr ; j++)
            if (v[i] > v[j])
                swap(v[i], v[j]);
}

int median(int st, int dr){
    int p, i;
    while (st != dr){
        for (i = st, p = st ; p + 5 <= dr ; p += 5, i++){
            selSort(p, p + 4);
            swap(v[i], v[p + 2]);
        }
        if (p != dr){
            selSort(p, dr);
            swap(v[i], v[(p + dr) >> 1]);
        } else
            i--;
        dr = i;
    }
    return v[st];
}

void qsort(int st, int dr){
    if (dr <= st) return;
/*
    if (dr - st <= 20)
        return selSort(st, dr);
*/

    int p = median(st, dr), i, j;
    for (i = st, j = dr ; i != j ; ){
        while (i != j && v[i] <= p)
            i++;
        while (i != j && p < v[j])
            j--;
        swap(v[i], v[j]);
    }

    qsort(st, i);
    qsort(i + 1, dr);
}

int main(){
    in >> n;
    for (int i = 0 ; i < n ; i++)
        in >> v[i];

    qsort(0, n - 1);

    for (int i = 0 ; i < n ; i++)
        out << v[i] << " ";
    out << "\n";

    return 0;
}