#include <fstream>
#include <algorithm>
#include <math.h>
#include <assert.h>
inline void print(int n) {
char snum[65];
int i = 0;
do {
snum[i++] = n % 10 + '0';
n /= 10;
} while (n);
--i;
while (i >= 0) {
putchar(snum[i--]);
}
putchar(' ');
}
inline int next_int() {
int n = 0;
char c = getchar_unlocked();
while (!('0' <= c && c <= '9')) {
c = getchar_unlocked();
}
while ('0' <= c && c <= '9') {
n = n * 10 + c - '0';
c = getchar_unlocked();
}
return n;
}
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 int partition(int v[], int left, int right) {
int pos = random() % (right - left + 1) + left;
int pivot = v[pos], i, j;
for (i = left, j = right; ;) {
for (; v[i] < pivot; ++i);
for (; v[j] > pivot ; --j);
if (i < j) {
std::swap(v[i++], v[j--]);
} else {
return j;
}
}
}
inline void quicksort(int v[], int left, int right) {
if (left >= right) {
return;
}
int mid = partition(v, left, right);
quicksort(v, left, mid);
quicksort(v, mid + 1, right);
}
inline void intro_sort_utils(int v[], int *begin, int *end, int max_depth, int n) {
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;
}
quicksort(v, 0, n - 1);
return;
}
inline void intro_sort(int v[], int *begin, int *end, int n) {
int max_depth = 2 * log(end - begin);
intro_sort_utils(v, begin, end, max_depth, n);
return;
}
int main() {
freopen("algsort.in", "r", stdin);
freopen("algsort.out", "w", stdout);
int n;
n = next_int();
assert(1 <= n && n <= 500000);
int v[n];
for (int i = 0 ; i < n ; ++i) {
v[i] = next_int();
}
intro_sort(v, v, v + n - 1, n);
for (int i = 0 ; i < n ; ++i) {
//printf("%d ", v[i]);
print(v[i]);
}
printf("\n");
return 0;
}