// mergesorter.cpp - implements MergeSorter
// cmc, 11/2/2013

#include "mergesorter.h"

// utility function to merge two array segments for mergesort
void merge(double values[], int leftFirst, int leftLast, 
           int rightFirst, int rightLast) {
    int size = rightLast - leftFirst + 1; 
    double *tempArray = new double[size];
    int index = leftFirst;
    int saveFirst = leftFirst;
    int it = 0;

    // merge array elements until one array runs out
    while ((leftFirst <= leftLast) && (rightFirst <= rightLast)) {
        if (values[leftFirst] < values[rightFirst])
            tempArray[it++] = values[leftFirst++];
        else
            tempArray[it++] = values[rightFirst++];
        index++;
    }
    
    // copy any remaining items from left half
    while (leftFirst <= leftLast) {
        tempArray[it++] = values[leftFirst++];
        index++;
    }
    
    // Copy any remaining items from right half
    while (rightFirst <= rightLast) {
        tempArray[it++] = values[rightFirst++];
        index++;
    }
    
    // finally copy back to values array, and free temp array
    it = 0;
    for (index = saveFirst; index <= rightLast; index++)
        values[index] = tempArray[it++];
    delete [] tempArray;
}

// recursive merge sort for double array
void mergesort(double values[], int first, int last) {
    if (first < last) {
        int middle = (first + last) / 2;
        mergesort(values, first, middle);
        mergesort(values, middle + 1, last);
        merge(values, first, middle, middle + 1, last);
    }
}

// first call just passes whole array to mergesort
void MergeSorter::sort(double x[], int n) {
    mergesort(x, 0, n-1);
}