merge_sort_2dim.cpp

void merge_sort(vector<int> &a, int left, int right) {
  // base case
  if (left + 1 >= right) {
    return;
  }

  // recursion case
  int mid = (left + right) / 2;
  merge_sort(a, left, mid);
  merge_sort(a, mid, right);

  // prepare left half for copy
  int size = mid - left;
  vector<vector<int>> v(size, vector<int>(2));
  for (int i = 0; i < size; i++) {
    v[i] = {a[left + i][0], a[left + i][1]};
  }

  // merge
  int i = 0;
  int j = mid;
  int k = left;

  while (i < size && j < right) {
    if (v[i][1] <= a[j][1]) { // sort by ascending endpoints
      a[k][0] = v[i][0];
      a[k][1] = v[i][1];
      k++;
      i++;
    } else {
      a[k][0] = a[j][0];
      a[k][1] = a[j][1];
      k++;
    }
  }
  while (i < size) {
    a[k][0] = v[i][0];
    a[k][1] = v[i][1];
    k++;
    i++;
  }
}