#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)>>1;
	int valPivot=v[pivot];
	
	int left=S,right=F;
	
	while(v[left]<valPivot) left++;
	while(v[right]>valPivot) right--;
	
	int mid=left;
	while(mid<=right)
	{
		// [s,left-1]<p, [left,mid-1]=p, [rigth+1,f]>p, [mid,right]-dunno
		if(v[mid]==valPivot) mid++;
		else 
		{
			if(v[mid]<valPivot) 
			{
				swap(v[mid],v[left]); left++;mid++;
			}
			else 
			{
				swap(v[mid],v[right]); right--;
			}
		}
	}
	
	
	if(left-1>S) qsort(S,left-1);
	if(F>right+1) qsort(right+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();
}