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

void swap(int*a, int*b);
int median_of_three(int *a, int st, int dr);
void quicksort(int*a, int st, int dr);
void printare(int *a, int n);

int main()
{
	int n, i;
	FILE *f = fopen("algsort.in", "r"), *g = fopen("algsort.out", "w");
	fscanf(f,"%d", &n);
	//int *a = (int*)malloc(sizeof(int)*n);
	int a[5000];
	for (i = 0; i < n; i++)
		fscanf(f,"%d", &a[i]);
	quicksort(a, 0, n - 1);
	for (i = 0; i < n; i++)
		fprintf(g,"%d ", a[i]);
	fclose(f); fclose(g);
	scanf("%d", &i);
	return 0;
}


void printare(int*a, int n)
{
	int i;
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}


void swap(int *a, int *b)
{
	int t = (*a);
	(*a) = (*b);
	(*b) = t;
}

int median_of_three(int *a, int st, int dr)
{
	int med = st + (dr - st) / 2;
	if (a[dr] < a[st])
		swap(&a[dr], &a[st]);
	if (a[med] < a[st])
		swap(&a[med], &a[st]);
	if (a[med]>a[dr])
		swap(&a[med], &a[dr]);
	return med;
}

int partitionare(int *a, int st, int dr)
{
	int i, j, piv, ok = 1;
	i = st - 1;
	j = dr + 1;
	piv = a[median_of_three(a,st,dr)];
	while (ok)
	{
		do
		{
			++i;
		} while (a[i]<piv);
		do
		{
			--j;
		} while (a[j]>piv);
		if (i < j)
		{

			swap(&a[i], &a[j]);
		}
		else
		{
			return j;
			ok = 0;
		}
	}
	return 0;
}

void quicksort(int*a, int st, int dr)
{
	if (st < dr)
	{
		int pivot = partitionare(a, st, dr);
		quicksort(a, st, pivot);
		quicksort(a, pivot + 1, dr);
	}
}