#include<fstream>
using namespace std;

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

int partition(int *a, int p, int r)
{
	int x, i, j;
	i = p - 1; // limita superioara a elementelor mai mici decat pivotul
	x = a[r]; // pivotul
	for(j = p; j < r; j++)
	{
		if(a[j] < x) // daca elem curent e mai mic decat pivotul
		{
			i++; // marim spatiul numerelor mai mici decat pivotul
			swap(a + i, a + j); // schimbam numarul mai mic decat x cu primul element care era mai mare ca x
			// a[j] va ajunge in multimea de nr. mai MICI decat pivotul
		}
	}
	swap(a + i + 1, a + r); // mutam pivotul la mijloc <=> il schimbam cu primul element mai mare ca el
	return i + 1;
}

void quickSort(int *a, int p, int r)
{
	if(p < r)
	{
		int q = partition(a, p, r);
		quickSort(a, p, q - 1);
		quickSort(a, q + 1, r);
	}
}

void Quick_Sort_Optim(int *a, int low, int high)
{
	while(low < high)
	{
		int k = partition(a, low, high);
		if(k - low > high - k) 
		{
			Quick_Sort_Optim(a, k + 1, high);
			high = k - 1;
		}
		else
		{
			Quick_Sort_Optim(a, low, k - 1);
			low = k + 1;
		}
	}
}

int main()
{
	ifstream fin("algsort.in");
	ofstream fout("algsort.out");
	int *a, n, i;
	fin >> n;
	a = new int[n];
	for(i = 0; i < n; i++)
		fin >> a[i];
	Quick_Sort_Optim(a, 0, n - 1);
	for(i = 0; i < n; i++)
		fout << a[i] << " ";
	return 0;
}