MergeSort

#include <iostream>
#include <vector>

// Слияние
void Merge(std::vector<int>& v, int l, int m, int r) {
  std::vector<int> result(r - l);
  int i = l;
  int j = m;
  while (i < m && j < r) {
    if (!(v[j] < v[i])) {
      result[i - l + j - m] = v[i]; ++i;
    } else {
      result[i - l + j - m] = v[j]; ++j;
    }
  }
  for (; i < m; ++i) result[i - l + j - m] = v[i];
  for (; j < r; ++j) result[j - l] = v[j];
  for (int k = 0; k < result.size(); ++k) v[l + k] = result[k];
}

// Сортировка на диапазоне [l, r)
void MergeSort(std::vector<int>& v, int l, int r) {
  if (r - l <= 1) return;
  int med = (r + l) / 2;
  MergeSort(v, l, med);
  MergeSort(v, med, r);
  Merge(v, l, med, r);
}

void MergeSort(std::vector<int>& v) {
  MergeSort(v, 0, v.size());
}

int main() {
  int n = 0;
  std::cin >> n;
  std::vector<int> v(n);
  for (int& x : v) std::cin >> x;
  MergeSort(v);
  for (int x : v) std::cout << x << " ";
  return 0;
}