#include <iostream>
#include <thread>
#include <algorithm>

using namespace std;

int N;

void mergesort_multithreaded(int *V, int left, int right, int threads) {
    if (left >= right)
        return;
    int mid = (left + right) / 2;
    if (threads >= 2) {
        thread a(mergesort_multithreaded, V, left, mid, threads - 2);
        mergesort_multithreaded(V, mid + 1, right, threads - 2);
        a.join();
    } else {
        mergesort_multithreaded(V, left, mid, 0);
        mergesort_multithreaded(V, mid + 1, right, 0);
    }
    inplace_merge(V + left, V + mid + 1, V + right + 1);
}

int main() {
    freopen("algsort.in", "r", stdin);
    freopen("algsort.out", "w", stdout);

    int i;

    scanf("%d", &N);
    int *V = new int[N];
    for (i = 0; i < N; ++i)
        scanf("%d", &V[i]);

    mergesort_multithreaded(V, 0, N - 1, 4);
    //sort(V, V + N);

    for (i = 0; i < N; ++i)
        cout << V[i] << ' ';

    return 0;
}