#include <fstream>
#include <algorithm>
#include <iostream>
#define NMAX 500001
 
using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");
 
int v[NMAX];
 
void qsort (int S, int F)
{
    int pivot=S+(F-S)/5;
	int valPivot=v[pivot];
	
	swap(v[F],v[pivot]);
	pivot=F;
	
	int wall=S;
	for(int i=S;i<F;i++)
		if(v[i]<valPivot)
		{
			swap(v[wall],v[i]);
			wall++;
		}
	
	swap(v[wall],v[pivot]);
	
	if(wall>S) qsort(S,wall-1);
	if(F>wall) qsort(wall+1,F);
}

int main()
{
    int N;
    f>>N;
 
    int i;
    for(i=1;i<=N;i++)
        f>>v[i];
 
    qsort(1,N);
 
    for(i=1;i<=N;i++)
        g<<v[i]<<' ';
	cout<<clock();
}