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

///// DESCRIPTION
// THIS PROGRAM EMPLOYS QUICKSORT
// TO ORDER A LIST OF N ELEMENTS
// IN ASCENDING ORDER
/////

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

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

inline void swap(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(0, n-1, v);
	//bubbleSort(n, v);
	//insertionSort(n, v);
	//selectionSort(n, v);
	//int out[n];
	//mergeSort(0, n-1, v, out);
	
	// OUTPUT
	ofstream outdata("algsort.out");
	for (int i = 0; i < n; i++) {
		outdata << v[i] << " ";
	}
	outdata.close();
	
	return 0;
}

void qsort(int ls, int ld, int v[]) {
	int middle = (ls + ld) / 2;
	int i = ls, j = ld;
	
	do {
		while (v[i] < v[middle]){
			i++;
		}
		while (v[j] > v[middle]) {
			j--;
		}
		
		if (i <= j) {
			swap(v[i], v[j]);
			i++; j--;
		}
	} while (i < j);

	if (j > ls) {
		qsort(ls, j, v);
	}
	if (i < ld) {
		qsort(i, ld, v);
	}
}
void mergeSort(int ls, int ld, int v[], int out[]) {
	if (ls == ld) {
		// base case
		out[0] = v[ls];
		return;
	}
	
	// get sorted sub lists
	int middle = (ls + ld) / 2;
	int leftSize = middle - ls + 1;
	int rightSize = ld - middle;
	
	int outLeft[leftSize], outRight[rightSize];
	mergeSort(ls, middle, v, outLeft);
	mergeSort(middle + 1, ld, v, 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++];
	}
	
	// copy sorted segment back to original
	for (int i = ls; i < ld; i++) {
		v[i] = out[i - ls];
	}
}

void bubbleSort(int n, int v[]) {
	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 n, int v[]) {
	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 n, int v[]) {
	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]);
	}
}


inline void swap(int& a, int& b) {
	int aux = a;
	a = b;
	b = aux;
}