#include <fstream>
#include <random>
#include <ctime>
#define nmax 500001
using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");
int N, i, A[nmax];
int choose_pivot(int *v, int left, int right) {
    int rand1 = left + rand() % (right - left + 1);
    srand(time(NULL) + 1);
    int rand2 = left + rand() % (right - left + 1);
    srand(time(NULL) + 2);
    int rand3 = left + rand() % (right - left + 1) ;
    if (v[rand1] > v[rand2]) swap(rand1, rand2);
    if (v[rand1] > v[rand3]) swap(rand1, rand3);
    if (v[rand2] > v[rand3]) swap(rand2, rand3);
    return rand2;
}
int partition_array(int *v, int left, int right, int pivot) {
    swap(v[pivot], v[right]);
    int i = left - 1, j = right;
    while (true) {
        i++;
        while (v[i] < v[right]) ++i;

        j--;
        while (v[j] > v[right]) --j;
        if (j <= i) {
            swap(v[j + 1], v[right]);
            return j + 1;
        }
        swap(v[i], v[j]);
    }
}
void qsort(int *v, int left, int right) {
    if(left >= right)
        return;
    int pivotPosition;
    int pivot = choose_pivot(v, left, right);
    pivotPosition = partition_array(v, left, right, pivot);
    qsort(v, left, pivotPosition - 1);
    qsort(v, pivotPosition + 1, right);

}
int main() {
    f >> N;
    for (i = 1; i <= N; i++)
        f >> A[i];
    qsort(A, 1, N);
    for (i = 1; i <= N; i++)
        g << A[i] << ' ';
    return 0;
}