#include <fstream>
#include <cmath>
using namespace std;

///// DESCRIPTION
// THIS PROGRAM IMPLEMENTS THE MOST
// POPULAR SORTING ALGORITHMS
// TO ORDER A LIST OF N ELEMENTS
// IN ASCENDINGLY
/////

void qsort(int[], int);
void qsort_aux(int[], int, int);
int qsortPartition(int[], int, int);

void mergeSort(int[], int);
void mergeSort_aux(int[], int, int, int[]);

void heapSort(int[], int);
void buildHeap(int[], int);
void heapify(int[], int, int);

void introSort(int[], int);
void introSort_aux(int[], int, int, int, int);

void bubbleSort(int[], int);
void insertionSort(int[], int);
void selectionSort(int[], int);

int main(int argc, char **argv)
{
	// INPUT
	ifstream indata("algsort.in");
	
	int n;
	indata >> n;
	
	int v[n];
	for (int i = 0; i < n; i++) {
		indata >> v[i];
	}
	
	indata.close();
	
	// SORT
	
	//qsort(v, n);
	//mergeSort(v, n);
	//heapSort(v, n);
	introSort(v, n);
	
	//bubbleSort(v, n);
	//insertionSort(v, n);
	//selectionSort(v, n);
	
	// OUTPUT
	ofstream outdata("algsort.out");
	for (int i = 0; i < n; i++) {
		outdata << v[i] << " ";
	}
	outdata.close();
	
	return 0;
}

// OPTIMUM ALGORITHMS
void qsort(int v[], int n) {
	qsort_aux(v, 0, n - 1);
}
void qsort_aux(int v[], int ls, int ld) {
	if (ls < ld) {
		int pivotIndex = qsortPartition(v, ls, ld);
		qsort_aux(v, ls, pivotIndex - 1);
		qsort_aux(v, pivotIndex + 1, ld);
	}
}
int qsortPartition(int v[], int ls, int ld) {
	const int middle = ls + (ld - ls) / 2; 
	const int pivot = v[middle];
	
	// move the pivot to the beginning 
	// of the current sub-array
	swap(v[middle], v[ls]);
	
	int i = ls + 1; int j = ld;
	
	while(i <= j) {
		while (i <= j && v[i] <= pivot){
			i++;
		}
		while (i <= j && v[j] >= v[middle]) {
			j--;
		}
		
		if (i < j) {
			swap(v[i], v[j]);
		}
	}
	
	// put the pivot back in its rightful position
	// and return what that position is
	swap(v[i - 1], v[ls]);
	return i - 1;
}

void mergeSort(int v[], int n) {
	int out[n];
	mergeSort_aux(v, 0, n - 1, out);
	
	// copy sorted segment back to original
	for (int i = 0; i < n; i++) {
		v[i] = out[i];
	}
}
void mergeSort_aux(int v[], int ls, int ld, int out[]) {
	if (ls == ld) {
		// base case
		out[0] = v[ls];
		return;
	}
	
	// get sorted sub lists
	int middle = ls + (ld - ls) / 2;
	int leftSize = middle - ls + 1;
	int rightSize = ld - middle;
	
	int outLeft[leftSize], outRight[rightSize];
	mergeSort_aux(v, ls, middle,  outLeft);
	mergeSort_aux(v, middle + 1, ld, outRight);
	
	// merge sort sub-lists
	int i = 0, x = 0, y = 0;
	while(x < leftSize && y < rightSize) {
		if (outLeft[x] < outRight[y]) {
			out[i++] = outLeft[x];
			x++;
		} else {
			out[i++] = outRight[y];
			y++;
		}
	}		
	while(x < leftSize) {
		out[i++] = outLeft[x++];
	}
	while (y < rightSize) {
		out[i++] = outRight[y++];
	}
}

void heapSort(int v[], int n) {
	buildHeap(v, n);
	
	for (int i = 0; i < n; i++) {
		swap(v[n - i - 1], v[0]);
		buildHeap(v, n - i - 1);
	}
}
void buildHeap(int v[], int n) {
	for (int i = n / 2; i > 0; i--) {
		heapify(v, i - 1, n);
	}
}
void heapify(int v[], int i, int n) {
	int root = i;
	int left = 2 * i + 1;
	int right = 2 * i + 2;
	
	if (left < n && v[root] < v[left]) {
		root = left;
	}
	if (right < n && v[root] < v[right]) {
		root = right;
	}
	
	if (root != i) {
		swap(v[i], v[root]);
		heapify(v, root, n);
	}
}

void introSort(int v[], int n) {
	introSort_aux(v, n, 0, n - 1, log(n) * 2);
}
void introSort_aux(int v[], int n, int ls, int ld, int maxdepth) {
	if (ls == ld) {
		return;
	}
	
	if (maxdepth == 0) {
		heapSort(v, n);
	} else {
		int pivotIndex = qsortPartition(v, ls, ld);
		introSort_aux(v, n, ls, pivotIndex - 1, maxdepth - 1);
		introSort_aux(v, n, pivotIndex + 1, ld, maxdepth - 1);
	}
}

// UNOPTIMUM ALGORITHMS
void bubbleSort(int v[], int n) {
	bool isOrdered = false;
	
	while(isOrdered == false) {
		isOrdered = true;
		for (int i = 0; i < n - 1; i++) {
			if (v[i] > v[i+1]) {
				swap(v[i], v[i+1]);
				isOrdered = false;
			}
		}
	}
}
void insertionSort(int v[], int n) {
	for (int i = 1; i < n; i++) {
		int j = i, aux = v[i];
		while(j > 0 && v[j - 1] > aux) {
			v[j] = v[j - 1];
			j--;
		}
		v[j] = aux;
	}
}
void selectionSort(int v[], int n) {
	for (int i = 0; i < n; i++) {
		int min = v[i], minIndex = i;
		for (int j = i + 1; j < n; j++) {
			if (v[j] < min) {
				min = v[j];
				minIndex = j;
			}
		}
		swap(v[i], v[minIndex]);
	}
}