/*********************************************************************
  C311 Spring 2021
  Authors: Dana Vrajitoru & W. Knight
  Functions implementing the merge sort.
********************************************************************/

#include <cstdlib>
#include "merge_sort.h"

/*********************  A R R A Y M E R G E ********************* 
This function assumes that the (sub)arrays a[afirst..alast] and
b[bfirst..blast] contain objects of a data type on which the binary
comparison operator "<=" is defined. It also assumes that the objects
in each array are arranged in increasing order.  It begins by making
sure that the (sub)array c[cfirst..clast] is large enough to hold all
the objects from the other two arrays; if that is not the case, it
returns the value false).  If it determines that the array c is big
enough, it copies all the objects from array a and b into array c in
such a way that they form a single ordered list in c .  Coded by
W. Knight and D. Vrajitoru, using a standard elementary merging
algorithm. */ 
 
bool merge_arrays (const int a[], int afirst, int alast, 
                   const int b[], int bfirst, int blast, 
                   int c[], int cfirst, int clast) 
{ 
    if (clast - cfirst + 1 < (alast - afirst + 1) + (blast - bfirst + 1)) 
        return false; 
    while (afirst <= alast && bfirst <= blast)    // While a and b both 
        if (a[afirst] <= b[bfirst])               // have objects that  
            c[cfirst++] = a[afirst++];            // are not yet copied, 
        else                                      // merge them into 
            c[cfirst++] = b[bfirst++];            // the array c. 
    // When the loop above terminates, at most one of the following 
    // two loops will have its loop condition true. 
    while (afirst <= alast)         // Copy the remaining objects from 
        c[cfirst++] = a[afirst++];  // array a into array c. 
    while (bfirst <= blast)         // Copy the remaining objects from 
        c[cfirst++] = b[bfirst++];  // array b into array c. 
    return true; 
} 

// The actual merge sort function
void merge_sort (int a[], int first, int last, int *aux) 
{ 
    if (last <= first) // a[first..last] has size 1 or less. If size  
        return;          // is 1 then the array is already sorted. 
    // This is the base case for the recursion. 
 
    bool initial_call = !(aux);    // Set to true if and only if aux 
    // is NULL. 
    if (initial_call) 
        aux = new int[last - first + 1]; //Allocate auxiliary space 

    int mid = (first + last) / 2; 
 
    merge_sort (a, first, mid, aux);     // Sort left subarray. 
    merge_sort (a, mid+1, last, aux);    // Sort right subarray. 
 
    // Merge the two sorted subarrays in "a" into the aux array. 
    // Ignore the boolean value returned by the merge function. 
 
    merge_arrays (a, first, mid, a, mid+1, last, aux, 0, last-first); 
 
    // Copy the sorted objects from aux back to "a". 
 
    for (int i = first, j = 0;  i <= last;  ++i, ++j) 
        a[i] = aux[j]; 
 
    if (initial_call)  // then the array pointed to by aux was 
        delete [] aux;   // allocated during this call. Deallocate it. 
}