#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);
	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);
	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;
}

void quicksort(int*a, int st, int dr)
{
	if (dr - st > 1)
	{
		int pivot = median_of_three(a, st, dr);
		int left = st, right = dr;
		while (left <= right)
		{
			while (a[left] < a[pivot])
				left++;
			while (a[right]>a[pivot])
				right--;
			if (left <= right)
			{
				swap(&a[left], &a[right]);
				left++;
				right--;
			}
		}
		quicksort(a, st, right);
		quicksort(a, left, dr);
	}
}