/**
*	Merge Sort Algorithm C++ Example by Codebind.com
*	Updated as follows by Dr. Spiegel
*		- use Meaningful Identifiers 
*		- proper C++ layout
*/
#include <iostream>

using namespace std;

void PrintArray(int *array, int elts);
void MergeSort(int arr[], int arr_size);

int main() {
  int array[] = {94, 42, 50, 95, 333, 65, 54, 456, 1, 1234};
  int elts = sizeof(array)/sizeof(array[0]);
  std::cout << "Before Merge Sort :" << std::endl;
  PrintArray(array, elts);
  MergeSort(array, elts);
  std::cout << "After Merge Sort :" << std::endl;
  PrintArray(array, elts);
  return (0);
}
 
void PrintArray(int *array, int elts) {
  for (int idx = 0; idx < elts; ++idx)
    std::cout << array[idx] << " " << std::flush;
  std::cout << std::endl;
}
 
void MergeLists(int arr[], int lo, int  mid, int hi){
    int *temp = new int[hi-lo+1];//temporary array to hold merged arrays
    int left_idx = lo, right_idx = mid + 1;	// left_idx is idx for left-hand, right_idx is idx for right-hand
    int temp_idx = 0;			// temp_idx is idx for the temporary array
    while(left_idx <= mid && right_idx <=hi){
        if(arr[left_idx] <= arr[right_idx])
            temp[temp_idx++] = arr[left_idx++];
        else
            temp[temp_idx++] = arr[right_idx++];
    }
    //rest elements of left-half
    while(left_idx <= mid)
        temp[temp_idx++] = arr[left_idx++];
    //rest elements of right-half
    while(right_idx <= hi)
        temp[temp_idx++] = arr[right_idx++];
    //copy the mergered temporary array to the original array
    for(temp_idx = 0, left_idx = lo; left_idx <= hi; ++left_idx, ++temp_idx)
        arr[left_idx] = temp[temp_idx];
 
    delete []temp;
}
void MergeSortHelper(int arr[], int lo, int hi){
    int mid;
    if(lo < hi){
        mid = (lo + hi) >> 1;
        MergeSortHelper(arr, lo, mid);
        MergeSortHelper(arr, mid+1, hi);
        MergeLists(arr, lo, mid, hi);
    }
}
void MergeSort(int arr[], int arr_size){
    MergeSortHelper(arr, 0, arr_size-1);
}