#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 + (rand() % (right - left + 1));   // 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)

{
	if (left < 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);
	}
}



void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];
 
      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
 
      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, 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;
}