Merge Sort

#include <bits/stdc++.h>

using namespace std;

void merge(vector <int>& a, int l, int r) {
  int i = l;
  int mid = (l + r) / 2;
  int j = mid + 1;
  vector <int> b(r - l + 1);
  int pos = 0;
  while (i <= mid && j <= r) {
    if (a[i] < a[j]) {
      b[pos++] = a[i++];
    } else {
      b[pos++] = a[j++];
    }
  }
  while (i <= mid) {
    b[pos++] = a[i++];
  }
  while (j <= r) {
    b[pos++] = a[j++];
  }
  for (int i = l; i <= r; i++) {
    a[i] = b[i - l];
  }
}

void merge_sort(vector <int>& a, int l, int r) {
  if (l >= r) {
    return;
  }
  int mid = (l + r) / 2;
  merge_sort(a, l, mid);
  merge_sort(a, mid + 1, r);
  merge(a, l, r);
}

int main() {
  int n;
  cin >> n;
  vector <int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  merge_sort(a, 0, n - 1);
  for (int i = 0; i < n; i++) {
    cout << a[i] << " ";
  }
}