#include <fstream>

using namespace std;

int a[500001];

void insertion(int l, int r){
    int i, j, v;
    for(i = l + 1; i <= r; i++){
        v = a[i];
        j = i - 1;
        while(j >= l && a[j] > v) {a[j+1] = a[j]; j--;}
        a[j+1] = v;
    }

}

int Partition( int d[], int left, int right)
{
	int val =d[left];
	int lm = left-1;
	int rm = right+1;
for(;;) {
		do
			rm--;
		while (d[rm] > val);

		do
			lm++;
		while( d[lm] < val);

		if(lm < rm) {
			int tempr = d[rm];
			d[rm] = d[lm];
			d[lm] = tempr;
			}
		else
			return rm;
		}
}


void quick(int l, int r){

    if(r - l - 1 > 8){

    int q = Partition(a, l, r);
        quick(l, q);
        quick(q+1, r);
    }
    else insertion(l, r);
}

int main(){
    ifstream f("algsort.in");
    ofstream g("algsort.out");
    int i = 0, n;
    f>>n;
    for(i = 0; i < n; i++)
        f>>a[i];
    quick(0, n-1);
    for(i = 0; i < n; i++)
        g<<a[i]<<" ";
    return 0;
}