#include <fstream>
#include <algorithm>
#include <math.h>
#include <assert.h>

inline void swap(int *a, int *b) {
	int *temp = std::move(a);
	a = std::move(b);
	b = std::move(temp);
}

inline void insertion_sort(int v[], int *begin, int *end) {
	int left = begin - v;
	int right = end - v;

	for (int i = left + 1; i <= right ; ++i) {
		int element = v[i];
		int j = i - 1;

		while ( j >= left && v[j] > element) {
			v[j + 1] = v[j];
			--j;
		}

		v[j + 1] = element;
	}

	return;
}

inline int* partition(int v[], int low, int high) {
	int pivot = v[high];
	int i = low - 1;

	for (int j = low ; j < high ; ++j) {
		if (v[j] <= pivot) {
			++i;
			std::swap(v[i], v[j]);
		}
	}

	std::swap(v[i + 1], v[high]);

	return (v + i + 1);
}

inline int* median(int v[], int *a, int *b, int *c) {
	int max = std::max(std::max(v[*a], v[*b]), v[*c]);
	int min = std::min(std::min(v[*a], v[*b]), v[*c]);
	int median = max ^ min ^ v[*a] ^ v[*b] ^ v[*c];

	if (median == v[*a]) {
		return a;
	}

	if (median == v[*b]) {
		return b;
	}

	return c;
}

inline void intro_sort_utils(int v[], int *begin, int *end, int max_depth) {
	int size = end - begin;

	if (size < 16) {
		insertion_sort(v, begin, end);
		return;
	}

	if (max_depth == 0) {
		std::make_heap(begin, end + 1);
		std::sort_heap(begin, end + 1);
		return;
	}

	int *pivot = median(v, begin, begin + size / 2, end);

	swap(pivot, end);
	int *partition_point = partition(v, begin - v, end - v);
	intro_sort_utils(v, begin, partition_point - 1, max_depth - 1);
	intro_sort_utils(v, partition_point + 1, end, max_depth - 1);

	return;
}

inline void intro_sort(int v[], int *begin, int *end) {
	int max_depth = 2 * log(end - begin);
	intro_sort_utils(v, begin, end, max_depth);
	return;
}

int main() {
	std::ifstream cin("algsort.in");
	std::ofstream cout("algsort.cout");
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin >> n;

	assert(1 <= n && n <= 500000);
	int v[n];

	for (int i = 0 ; i < n ; ++i) {
		cin >> v[i];
	}

	intro_sort(v, v, v + n - 1);

	for (int i = 0 ; i < n ; ++i) {
		cout << v[i] << " ";
	}

	cout << '\n';
	return 0;
}