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

class Sorter {
public:
	Sorter(vector<int> V) : S(V), lower(V.size()), higher(V.size()) {
		srand(time(0));
		qsort(0, V.size() - 1);
	}

	int operator[](int i) { return S[i]; }

private:
	vector<int> S;
	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);
	}
};

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(V);
	for (int i=0; i<N; ++i) out << S[i] << " ";
	out << "\n";
	return 0;
}