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

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define MAX     500000 
unsigned short int numere[MAX];

void interschimb (unsigned short int *a, unsigned short int *b) {
	unsigned short 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;
	unsigned short 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, "%hd", &numere[i]);
	quicksort(0, n - 1);
	for (i = 0; i < n; i++)
		fprintf(f_out, "%hd ", numere[i]);
	return 0;
}