#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--;
	
	for(int i=left;i<=right;i++)
	{
		if(v[i]<valPivot)
			swap(v[left++],v[i]);	
		
		else if(v[i]>valPivot)
			swap(v[right--],v[i]);
	}
	
	
	if(left>S) qsort(S,left-1);
	if(F>right) 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]<<'\n';
	cout<<clock();
}