#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

const int NMAX = 500000;

inline int mid(int a, int b, int c) {
    if (a > b) {
        if (b > c) {
            return b;
        } else if (a > c) {
            return c;
        } else {
            return a;
        }
    } else {
        if (a > c) {
            return a;
        } else if (b > c) {
            return c;
        } else {
            return b;
        }
    }
}

inline int randbetween(int i, int j) {
    return rand() % (j - i + 1) + i;
}

inline int pivot(int v[], int i, int j) {
    if (j - i + 1 < 10) {
        return v[randbetween(i, j)];
    }

    int a = randbetween(i, j);
    int b = randbetween(i, j);
    int c = randbetween(i, j);

    return mid(v[a], v[b], v[c]);
}

inline void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

void sortare(int v[], int x, int y) {
    if (y - x + 1 <= 2) {
        if (v[x] > v[y]) swap(v[x], v[y]);

        return;
    }

    int i = x, j = y;
    int piv = pivot(v, i, j);
    while (i < j) {
        while (v[i] < piv) i++;
        while (piv < v[j]) j--;

        if (i < j) {
            swap(v[i], v[j]);
            i++; j--;
        }
    }

    sortare(v, x, j);
    sortare(v, i, y);
}

int main() {
    srand(time(NULL));

    int n, v[NMAX];

    FILE * in = fopen("algsort.in", "r");
    fscanf(in, "%d", &n);
    for (int i = 0; i < n; ++i)
        fscanf(in, "%d", &v[i]);
    fclose(in);

    sortare(v, 0, n-1);

    FILE * out = fopen("algsort.out", "w");
    for (int i = 0; i < n; ++i)
        fprintf(out, "%d ", v[i]);
        //printf("%d ", v[i]);
    fclose(out);

    return 0;
}