#include <stdio.h>
#include <ctype.h>
#include <stdint.h>

#define MAX_N 500000
#define BUFF_SIZE (1 << 12)
#define SIZE 16

const 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 };

uint_fast32_t v[MAX_N];
uint_fast32_t deph;
char buff[BUFF_SIZE];
uint_fast32_t pos = BUFF_SIZE;
FILE *f;

inline char get() {
    if (pos == BUFF_SIZE) {
       fread(buff, 1, BUFF_SIZE, f);
       pos = 0;
    }
    return buff[pos++];
}
inline uint_fast32_t readINT() {
    char c;
    uint_fast32_t 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(uint_fast32_t lo, uint_fast32_t hi) {
    uint_fast32_t t;

    for (uint_fast32_t i = lo; i <= hi; ++i) {
        t = v[i];
        uint_fast32_t j = i;
        while (j > lo && t < v[j - 1]) {
            v[j] = v[j - 1];
            --j;
        }
        v[j] = t;
    }
}
inline void downheap(uint_fast32_t i, uint_fast32_t n, uint_fast32_t lo) {
    if(i > n >> 1)
        return;
    uint_fast32_t d = v[lo + i - 1];
    uint_fast32_t 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(uint_fast32_t lo, uint_fast32_t hi) {
    uint_fast32_t n = hi - lo;

    for (uint_fast32_t i = n >> 1; i >= 1; --i) {
        downheap(i, n, lo);
    }
    for (uint_fast32_t i = n; i > 1; --i) {
        uint_fast32_t aux = v[lo];
        v[lo] = v[lo + i - 1];
        v[lo + i - 1] = aux;
        downheap(1, i - 1, lo);
    }
}
inline uint_fast32_t med3(uint_fast32_t a, uint_fast32_t b, uint_fast32_t 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 uint_fast32_t partitie(uint_fast32_t lo, uint_fast32_t hi, uint_fast32_t x) {
    uint_fast32_t i = lo;
    uint_fast32_t 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(uint_fast32_t lo, uint_fast32_t hi) {
    while (hi - lo > SIZE) {
        if (!deph) {
           // continui cu un heapsort
           heapsort(lo, hi);
           return;
        }
        --deph;
        uint_fast32_t p = partitie(lo, hi, med3(lo, lo + ((hi - lo) >> 1) + 1, hi));
        introsort(p, hi);
        hi = p;
    }
    insertion(lo, hi);
}

inline uint_fast32_t log2(uint_fast32_t 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) {
    uint_fast32_t n;
    register uint_fast32_t i;

    f = fopen("algsort.in", "r");
    n = readINT();
    for (i = 0; i < n - 3; i += 4) {
        v[i] = readINT();
        v[i + 1] = readINT();
        v[i + 2] = readINT();
        v[i + 3] = readINT();
    }
    for ( ; i < n; ++i) {
        v[i] = readINT();
    }
    fclose(f);

    deph = log2(n) << 1;
    introsort(0, n - 1);

    f = fopen("algsort.out", "w");
    for (i = 0; i < n; ++i)
        fprintf(f, "%d ", v[i]);
    fclose(f);
    return 0;
}