#include <stdio.h>
#include <ctype.h>
#define MAX_N 500000
#define BUFF_SIZE (1 << 12)
#define SIZE 16
int table[32] = {
0, 9, 1, 10, 13, 21, 2, 29,
11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7,
19, 27, 23, 6, 26, 5, 4, 31 };
int v[MAX_N];
int deph;
char buff[BUFF_SIZE];
int pos = BUFF_SIZE;
FILE *f;
inline char get() {
if (pos == BUFF_SIZE) {
fread(buff, 1, BUFF_SIZE, f);
pos = 0;
}
return buff[pos++];
}
inline int readINT() {
char c;
int nr = 0;
do {
c = get();
} while(!isdigit(c));
do {
nr = (nr << 1) + (nr << 3) + (c - '0');
c = get();
} while(isdigit(c));
return nr;
}
void insertion(int lo, int hi) {
int t;
for (int i = lo; i <= hi; ++i) {
t = v[i];
int j = i;
while (j > lo && t < v[j - 1]) {
v[j] = v[j - 1];
--j;
}
v[j] = t;
}
}
void downheap(int i, int n, int lo) {
if(i > n >> 1)
return;
int d = v[lo + i - 1];
int child;
do {
child = i << 1;
if (child < n && v[lo + child - 1] < v[lo + child]) {
++child;
}
if (d < v[lo + child - 1]) {
v[lo + i - 1] = v[lo + child - 1];
i = child;
}
} while(i <= n >> 1 && d < v[lo + child - 1]);
v[lo + i - 1] = d;
}
void heapsort(int lo, int hi) {
int n = hi - lo;
for (int i = n >> 1; i >= 1; --i) {
downheap(i, n, lo);
}
for (int i = n; i > 1; --i) {
int aux = v[lo];
v[lo] = v[lo + i - 1];
v[lo + i - 1] = aux;
downheap(1, i - 1, lo);
}
}
inline int med3(int a, int b, int c) {
if (v[a] < v[b]) {
if (v[b] < v[c])
return v[b];
return v[c];
}
if (v[a] < v[c])
return v[a];
return v[c];
}
inline int partitie(int lo, int hi, int x) {
int i = lo;
int j = hi;
while (i <= j) {
while (v[i] < x)
++i;
while (v[j] > x)
--j;
if (i <= j) {
int aux = v[i];
v[i] = v[j];
v[j] = aux;
++i;
--j;
}
}
return i;
}
void introsort(int lo, int hi) {
while (hi - lo > SIZE) {
if (!deph) {
// continui cu un heapsort
heapsort(lo, hi);
return;
}
--deph;
int p = partitie(lo, hi, med3(lo, lo + ((hi - lo) >> 1) + 1, hi));
introsort(p, hi);
hi = p;
}
insertion(lo, hi);
}
int log2(int val) {
val |= val >> 1;
val |= val >> 2;
val |= val >> 4;
val |= val >> 8;
val |= val >> 16;
return table[(unsigned)(val * 0x07C4ACDD) >> 27];
}
int main (void) {
int n;
f = fopen("algsort.in", "r");
n = readINT();
for (int i = 0; i < n; ++i)
v[i] = readINT();
fclose(f);
deph = log2(n) << 1;
introsort(0, n - 1);
f = fopen("algsort.out", "w");
for (int i = 0; i < n; ++i)
fprintf(f, "%d ", v[i]);
fclose(f);
return 0;
}