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

#define SIZE(x, y) y - x + 1
#define SWAP(x, y) x^=y^=x^=y
#define NMAX 500000

void insertionSort(unsigned long int *arr, int start, int size)
{
	int i, temp, j;
	for(i = start + 1; i < start + size; ++i)
	{
		temp = arr[i];
		j = i-1;
		while(temp < arr[j] && j >= start)
		{
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = temp;
	}
}

int partition(unsigned long int *arr, unsigned int lo, unsigned int hi)
{
	unsigned int pivot = arr[lo + (rand() % (SIZE(lo, hi)))];

	while(lo < hi)
	{
		while(arr[lo] < pivot) lo++;
		while(arr[hi] > pivot) hi--;
		if(lo < hi) SWAP(arr[lo], arr[hi]);
	}
	return lo;
}

void sort(unsigned long int *arr, unsigned int lo, unsigned int hi)
{
	unsigned int index;
	if(SIZE(lo, hi) >= 10)
	{
		index = partition(arr, lo, hi);
		sort(arr, lo, index - 1);
		sort(arr, index, hi);
	}
	else
		insertionSort(arr, lo, SIZE(lo, hi));
}

void quickSort(unsigned long int *arr, int size)
{
	sort(arr, 0, size-1);
}

int main()
{
	unsigned long int *arr = NULL;
	unsigned int i;
	unsigned int size;
	FILE *fpi = fopen("algsort.in", "r");
	FILE *fpo = fopen("algsort.out", "w");
	arr = (unsigned long int*)malloc(sizeof(unsigned long int) * NMAX);

	fscanf(fpi, "%d", &size);
	for(i = 0; i < size; ++i)
		fscanf(fpi, "%d", &arr[i]);

	quickSort(arr, size);

	for(i = 0; i < size; ++i)
		fprintf(fpo, "%d ", arr[i]);

	fclose(fpo);
	fclose(fpi);
	free(arr);

	return 0;
}