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

void read(FILE *f, int *a, int N)
{
	int i;

	for (i = 0; i < N; i++)
		fscanf(f, "%d", a + i);
}

void print(FILE *g, int *a, int N)
{
	int i;

	for (i = 0; i < N; i++)
		fprintf(g, "%d ", a[i]);
}

void swap(int *a, int i, int j)
{
	int tmp = a[i];
	   a[i] = a[j];
	   a[j] = tmp;
}

void randomXchg(int *a, int start, int end)
{
	srand(time(NULL));
	int rnd = random();
	rnd = rnd % (end - start);
	swap(a, start, start + rnd);
}

int partition(int *a, int start, int end)
{
	randomXchg(a, start, end);

	int x = a[start], j = start, i;

	for (i = start + 1; i <= end; i++)
		if (a[i] < x) {
			j++;
			swap(a, i, j);
		}
	swap(a, start, j);
	return j;
}

void quicksort(int *a, int start, int end)
{
	int q;

	if (end > start) {
		q = partition(a, start, end);
		quicksort(a, start, q - 1);
		quicksort(a, q + 1, end);
	}
}


int main()
{
	FILE *f = NULL , *g = NULL;
	int N, *a = NULL;
	f = fopen("algsort.in", "rt");
	g = fopen("algsort.out", "wt");

	fscanf(f, "%d", &N);
	a = malloc(N * sizeof(int));

	read(f, a, N);
	quicksort(a, 0, N-1);

	print(g, a, N);

	fclose(f);
	fclose(g);
	free(a);
	return 0;
}