#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <fstream>


#define N 17
#define MAX 500005

using namespace std;

void swap(int * x, int * y)
{
	int aux = *x;
	*x = *y;
	*y = aux; 
}

int run_pivot(int v[], int left, int right)
{
	int pivotindex = left + (right - left + 1) / 2; //left + (right - left + 1) / 4 + (rand() % ((right - left + 1) / 2));
	int i,storeindex = left;
	int pivot = v[ pivotindex ];
	
	swap(v + pivotindex, v + right);
	pivotindex = right;
	
	for (i = left; i < right; i++)
	{
		if (v[i] <= pivot)
		{
			swap(v + storeindex, v + i);
			storeindex ++;
		}
	}
	swap(v + storeindex, v + pivotindex);
	return storeindex;
	
}

void qsort_mine(int v[], int left, int right)

{
	int pivotindex = run_pivot(v,left,right);
	if (left < pivotindex - 1)
		qsort_mine(v, left, pivotindex - 1);
	if (pivotindex + 1 < right)
		qsort_mine(v,pivotindex + 1,right);
}





int main()
{
	//srand(time(NULL));
	int v[MAX], n, i;
	ifstream f("algsort.in");
	ofstream g("algsort.out");
	f >> n;
	for (i = 0; i < n; i++)
	{
		//fscanf(f, "%i", v + i);
		f >> v[i];
	}
	
	qsort_mine(v, 0, n-1);

	for (i = 0; i < n; i++)
		//fprintf(f, "%i ", v[i]);
		g << v[i] << " ";
	
	return 0;
}