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

#define N 17
#define MAX 500000

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

int run_pivot(int v[], int left, int right)
{
	srand(time(NULL));

	int pivotindex = left + (right - left + 1) / 4 + (rand() % ((right - left + 1) / 2) + 1);
	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()
{
	int v[MAX], n, i;
	FILE *f = fopen("algsort.in","r");
	fscanf(f,"%i",&n);
	for (i = 0; i < n; i++)
	{
		fscanf(f, "%i", v + i);
	}
	fclose(f);
	f = fopen("algsort.out", "w");
	qsort_mine(v, 0, n-1);

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

	return 0;
}