/*
 * Randomized Quicksort which switches to selection sort
 * when the size of the subarray is smaller than sw.
 * Also we use 3-way partitioning i.e. in the partitioning 
 * step we use two pivots and partition the array into 
 * three: strictly smaller, equal and strictly larger.
 */
#include <fstream>
#include <cstdlib>
using namespace std;

ifstream fin("algsort.in");
ofstream fout("algsort.out");

int sw = 16; /* the value at which the algorithm switches to selection sort */
int v[500001], n;

void quicksort(int l, int r)
{
	int i, j, q, aux;
	if(r - l > sw) /* if the size of the subarray is larger than sw we use quicksort */
	{
        /* pick a random element from the subarray */
		i = l + rand() % (r-l+1);
		/* set the random element to be the pivot */
		aux = v[i]; v[i] = v[r]; v[r] = aux;

		/* do the 3-way partitioning */
		for(i = l-1, q = l-1, j = l; j <= r-1; j++)
			if(v[j] <= v[r])
			{
				aux = v[++i]; v[i] = v[j]; v[j] = aux;
				if(v[i] < v[r] && (++q) != i)
					   aux = v[q], v[q] = v[i], v[i] = aux;
			}
		/* put the pivot in its correct place in the subbarray */
		aux = v[++i]; v[i] = v[r]; v[r] = aux;
		/* finished partitioning */

		quicksort(l, q);
		quicksort(i+1, r);
    	
	}        
	else if(l < r) /* if the size of the subarray is smaller than sw we use insertion sort */
		for(i = l+1; i <= r; ++i)
			for(j = i-1; j >= l && v[j] > v[j+1]; --j)
				aux = v[j], v[j] = v[j+1], v[j+1] = aux;
}

int main()
{
    int i;
	srand(16); /* seed value for the RNG */
	
	fin >> n;
	for(i = 1; i <= n; ++i)
		fin >> v[i];

	quicksort(1, n);

	for(i = 1; i <= n; ++i)
		fout << v[i] << ' ';
	fout << endl;

	fin.close();
	fout.close();
	return 0;
}