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

class Sorter {
public: 
	Sorter(vector<int> V) : S(V) {}
	int operator[](int i) { return S[i]; }

protected:
	vector<int> S;
};

class QSorter : public Sorter {
public:
	QSorter(vector<int> V) : Sorter(V), lower(V.size()), higher(V.size()) {
		cerr << "Using quick sort" << endl;
		srand(time(0));
		qsort(0, V.size() - 1);
	}

private:
	vector<int> lower;
	vector<int> higher;

	void qsort(int a, int b) {
		// cerr << "SORTING " << a << " " << b << endl;
		if (a >= b) return;

		// for (int i=a; i<=b; ++i) cerr << S[i] << " "; cerr << endl;

		int pivot = rand() % (b-a+1) + a;
		int X = S[pivot];
		// cerr << "PIVOT " << pivot << " " << X << endl;

		int equal = 0;
		int l = 0, h = 0;
		for (int i=a; i<=b; ++i) {
			if (S[i] < X) {
				lower[l ++] = S[i];
			} else if (S[i] == X) {
				equal ++;
			} else {
				higher[h ++] = S[i];
			}
		}

		// cerr << "LEH " << l << " " << equal << " " << h << endl;
		
		for (int i=0; i<l; ++i) S[a+i] = lower[i];
		for (int i=0; i<equal; ++i) S[a+l+i] = X;
		for (int i=0; i<h; ++i) S[a+l+equal+i] = higher[i];

		// for (int i=a; i<=b; ++i) cerr << S[i] << " "; cerr << endl;

		qsort(a, a+l-1);
		qsort(a+l+equal, b);
	}
};

class MSorter : public Sorter {
public:
	MSorter(vector<int> V) : Sorter(V), tmp(V.size()) {
		cerr << "Using merge sort" << endl;
		msort(0, V.size() - 1);
	};

private:
	vector<int> tmp; 

	void msort(int a, int b) {
		if (a >= b) return;

		int m = (a+b) / 2;
		msort(a, m);
		msort(m+1, b);

		int l=a, r=m+1, i;
		for (i=0; l<=m && r <=b; ++i) {
			if (S[l] < S[r]) tmp[i] = S[l++];
			else tmp[i] = S[r++];
		}
		for (; l<=m; ++l, ++i) tmp[i] = S[l];
		for (; r<=b; ++r, ++i) tmp[i] = S[r];

		copy(tmp.begin(), tmp.begin() + b - a + 1, S.begin() + a);
	}
};

int main() {
	ifstream in("algsort.in");
	ofstream out("algsort.out");

	int N;
	in >> N;
	vector<int> V(N);
	for (int i=0; i<N; ++i) {
		in >> V[i];
	}

	Sorter* S = new MSorter(V);
	for (int i=0; i<N; ++i) out << (*S)[i] << " ";
	out << "\n";

	delete S;
	return 0;
}