#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iostream>
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);
void qsortPartition(int[], int&, int&);
int int_compare_asc(const void*, const void*);

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

void heapSort(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) {
	// STL IMPLEMENTATION
	std::qsort(v, n, sizeof(int), int_compare_asc);
	
	// OWN IMPLEMENTATION
	qsort_aux(v, 0, n - 1);
}
void qsort_aux(int v[], int ls, int ld) {
	if (ls < ld) {
		int i = ls, j = ld;
		qsortPartition(v, i, j);

		qsort_aux(v, ls, j);
		qsort_aux(v, i, ld);
	}
}
void qsortPartition(int v[], int& ls, int& ld) {
	const int middle = ls + (ld - ls) / 2; 
	const int pivot = v[middle];	
	int i = ls, j = ld;
	
	while(i < j) {
			while(i < ld && v[i] < pivot) {
				i++;
			}
			while(j > ls && v[j] > pivot) {
				j--;
			}
			
			if(i <= j){
				swap(v[i], v[j]);
				i++; j--;
			}
		}
	
	ls = i;
	ld = j;
}
int int_compare_asc(const void* a, const void* b) {
  return ( *(int*)a - *(int*)b );
}

void mergeSort(int v[], int n) {
	mergeSort_aux(v, 0, n - 1);
}
void mergeSort_aux(int v[], int ls, int ld) {
	if (ls < ld) {
		int middle = ls + (ld - ls) / 2;
		mergeSort_aux(v, ls, middle);
		mergeSort_aux(v, middle + 1, ld);
		merge(v, ls, middle, ld);
	}
}
void merge(int v[], int ls, int middle, int ld) {
	int i = 0, x = ls, y = middle + 1;
	int aux[ls + ld + 1];
	
	while(x <= middle && y <= ld) {
		if (v[x] < v[y]) {
			aux[i++] = v[x];
			x++;
		} else {
			aux[i++] = v[y];
			y++;
		}
	}		
	while(x <= middle) {
		aux[i++] = v[x++];
	}
	while (y <= ld) {
		aux[i++] = v[y++];
	}
	
	// copy the new merged sub-list 
	// in the original position in the array
	for (i = ls; i <= ld; i++) {
		v[i] = aux[i - ls];
	}
}

void heapSort(int v[], int n) {
	//STL implementation
	//std::vector<int> unorderedList(v, v + n);
	//std::make_heap(unorderedList.begin(), unorderedList.end());
	//std::sort_heap(unorderedList.begin(), unorderedList.end());
	//std::copy(unorderedList.begin(), unorderedList.end(), v);
	
	// own implementation
	for (int i = n / 2; i > 0; i--) {
		heapify(v, i - 1, n);
	}

	for (int i = 0; i < n; i++) {
		swap(v[n - i - 1], v[0]);
		heapify(v, 0, n - i - 1);
	}
}
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 i = ld, j = ld;
		qsortPartition(v, i, j);
		
		introSort_aux(v, n, ls, j, maxdepth - 1);
		introSort_aux(v, n, i, 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]);
	}
}