#include <iostream>       // std::cout
#include <thread>         // std::thread, std::this_thread::sleep_for
#include <chrono>         // std::chrono::seconds


const int MAX_N = 1000000;
int v[MAX_N];
int aux[MAX_N];
std::thread thr[MAX_N];

void interclasare(int st, int mid, int dr) {
  int i = st, j = mid, k = st;
  int n1 = mid, n2 = dr;

  while(i < n1 || j < n2) {
    if(i < n1 && j < n2 && v[i] < v[j])
      aux[k] = v[i++];
    else if(i < n1 && j < n2)
      aux[k] = v[j++];
    else if(i < n1)
      aux[k] = v[i++];
    else
      aux[k] = v[j++];
    ++k;
  }

  for(i = st; i < dr; ++i)
    v[i] = aux[i];
}

inline int min(int a, int b) {
  if(a < b)
    return a;
  return b;
}

void mergesort(int *v, int n) {
  int p2 = 1, nthr, st;
  while(p2 < n) {
    nthr = 0;
    st = 0;
    while(st < n) {
      thr[nthr++] = std::thread(interclasare, st, st + p2, min(st + 2 * p2, n));
      st = st + 2 * p2;
    }
    for(int i = 0; i < nthr; ++i)
      thr[i].join();

    p2 = p2 * 2;
  }
}

int main() {
  int n;
  FILE *fin = fopen("algsort.in", "r");
  fscanf(fin, "%d", &n);
  for(int i = 0; i < n; ++i)
    fscanf(fin, "%d", &v[i]);
  fclose(fin);

  mergesort(v, n);

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