/* 
Algoritm de sortare prin comparare - QuickSort.
*/

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

#define MAX     500000

int numere[MAX];

void interschimb (int *a, int *b) {
    int aux;

    aux = *a;
    *a = *b;
    *b = aux;
}

void quicksort (int start, int stop) {
    int i = start - 1;
    int j = stop;
    int p = start - 1;
    int q = stop;

    int temp = numere[stop];

    if (stop <= start)
        return;
    while (1) {
        while (numere[++i] < temp)
            ;
        while (temp < numere[--j])
            if (j == start)
                break;
        if (i >= j)
            break;
        interschimb(&numere[i], &numere[j]);
        if (numere[i] == temp) {
            p++;
            interschimb(&numere[p], &numere[i]);
        }
        if (numere[j] == temp) {
            q--;
            interschimb(&numere[j], &numere[q]);
        }
    }
    interschimb(&numere[i], &numere[stop]);
    j = i - 1;
    i++;
    int k;
    for (k = start; k < p; k++, j--)
        interschimb(&numere[k], &numere[j]);
    for (k = stop - 1; k > q; k--, i++)
        interschimb(&numere[i], &numere[k]);
    quicksort(start, j);
    quicksort(i, stop);
}

int main () {
    FILE *f_in = fopen("algsort.in", "r");
    FILE *f_out = fopen("algsort.out", "w");

    int n;
    int i;

    fscanf(f_in, "%d", &n);
    for (i = 0; i < n; i++)
        fscanf(f_in, "%d", &numere[i]);

    quicksort(0, n - 1);
    for (i = 0; i < n; i++)
        fprintf(f_out, "%d ", numere[i]);
    return 0;
}