merge_sort.cc

#include <iostream>
#include <string>
#include <cmath>

using std::cout;
using std::endl;
using std::string;

void merge(int*, int, int, int);
void mergesort(int*, int, int);
void print(int*, int);

int main() {
  int array[] = { 2, 4, 5, 7, 1, 2, 3, 6 };
  int size = sizeof(array)/sizeof(int);

  print(array, size);
  merge(array, 1, size/2, size);
  print(array, size);

  return 0;
}

void merge(int *array, int p, int q, int r) {
  int n1 = q - p + 1;
  int n2 = r - q;

  int *left = new int[n1];
  int *right = new int[n2];

  for(int i = 0; i != n1; ++i)
    *(left + i) = array[p + i - 1];

  for(int j = 0; j != n2; ++j)
    *(right + j) = array[q + j];

  left[n1] = 1000000; //sentinel
  right[n2] = 1000000; //sentinel
  
  int i = 0, j = 0;

  for(int k = 0; k < r; ++k) {
    if(left[i] <= right[j]) {
      array[k] = left[i];
      ++i;
    } else if(right[j] < left[i]) {
      array[k] = right[j];
      ++j;
    }
  }

  delete [] left;
  delete [] right;

}

void mergesort(int* array, int p, int r) {
  if(p < r) {
    int q = floor((p + r) / 2);
    mergesort(array, p, q);
    mergesort(array, q + 1, r);
    merge(array, p, q, r);
  }
}

void print(int *array, int size) {  
  int *i = array, *j = array + size;
  cout << "[ ";
  for( ; i != j; ++i)
    cout << *i << ", "; 
  cout << " ]" << endl;
}