#include <stdio.h>
#include <stdlib.h>

FILE *fin, *fout;

int a[500000];

void swap(int *p1, int *p2) {
    int aux = *p1;
    *p1 = *p2;
    *p2 = aux;
}

void partition(int v[], int st, int dr, int *p1, int *p2) {
    int poz = rand() % (dr - st + 1) + st;
    swap(&v[poz], &v[dr]);
    *p1 = st;
    *p2 = dr - 1;
    int i = st;
    while(i <= *p2) {
        if(v[i] == v[dr])
            ++i;
        else if(v[i] < v[dr])
            swap(&v[(*p1)++], &v[i++]);
        else
            swap(&v[(*p2)--], &v[i]);
    }
    swap(&v[++(*p2)], &v[dr]);
}

void quicksort(int v[], int st, int dr) {
    while(st < dr) {
        int p1, p2;
        partition(v, st, dr, &p1, &p2);

        if(p1 - st < dr - p2) {
            quicksort(v, st, p1 - 1);
            st = p2 + 1;
        } else {
            quicksort(v, p2 + 1, dr);
            dr = p1 - 1;
        }
    }
}

int main(void) {
    srand(1989);
    fin = fopen("algsort.in", "r");
    int n;
    fscanf(fin, "%d", &n);
    for(int i = 0; i < n; ++i) {
        fscanf(fin, "%d", &a[i]);
    }
    fclose(fin);
    quicksort(a, 0, n-1);
    fout = fopen("algsort.out", "w");
    for(int i = 0; i < n; ++i) {
        fprintf(fout, "%d ", a[i]);
    }
    fprintf(fout, "\n");
    fclose(fout);

    return 0;
}