mergeSort.cpp

#include <iostream>

using namespace std;

void Merge (int* a, int left, int mid, int right) {
  int it1 = 0, it2 = 0;
  int result[right - left];

  while ((left + it1 < mid) && (mid + it2 < right)) {
    if (a[left + it1] < a[mid + it2]) {
      result[it1 + it2] = a[left + it1];
      it1 += 1;
    } else {
      result[it1 + it2] = a[mid + it2];
      it2 += 1;
    }
  }

  while (left + it1 < mid) {
    result[it1 + it2] = a[left + it1];
    it1 += 1;
  }

  while (mid + it2 < right) {
    result[it1 + it2] = a[mid + it2];
    it2 += 1;
  }

  for (int i = 0; i < it1 + it2; ++i) {
    a[left + i] = result[i];
  }
}

void MergeSort (int* a, int left, int right) {
  if (left + 1 >= right) {
    return;
  }

  int mid = (left + right) / 2;

  MergeSort(a, left, mid);
  MergeSort(a, mid, right);
  Merge(a, left, mid, right);
}