#include <bits/stdc++.h>

using namespace std;

ifstream f("algsort.in");
ofstream g("algsort.out");

int arr[3000001];

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

int median(int left, int right)
{
	int r1 = rand () % (right - left + 1) + left;
	int r2 = rand () % (right - left + 1) + left;
	int r3 = rand () % (right - left + 1) + left;
	if(arr[r1] <= arr[r2] && arr[r1] <= arr[r3])
		return ( (arr[r2] < arr[r3]) ? arr[r2]:arr[r3]);
	if(arr[r2] <= arr[r3] && arr[r2] <= arr[r1])
		return ( (arr[r3] < arr[r1]) ? arr[r3]:arr[r1]);
	if(arr[r3] <= arr[r1] && arr[r3] <= arr[r2])
		return ( (arr[r1] < arr[r2]) ? arr[r1]:arr[r2]);

}

int quickSort(int left, int right)
{
	int pivot = median(left, right);
	int i, j;
	i = left;
	j = right;
	while(i <= j){
		while(arr[i] < pivot) i++;

		while(arr[j] > pivot) j--;
		
		if( i <= j) {
			swap(arr[i], arr[j]);
			i++;
			j--;
		}

		
	}
	if(i < right) quickSort(i, right);
	if(j > left) quickSort(left, j);


}


int main()
{
	
	int n;
	f>>n;
	for(int i = 1; i <= n; i++) f>>arr[i];
	srand(time(NULL));
    quickSort(1, n);
    for(int i = 1; i <= n; i++) g<<arr[i]<<" ";
    f.close();
    g.close();
    return 0;

}