#include "Array.h"

template <typename T>
void MergeSort(Array<T> &ra);

template <typename T>
void MergeSortRec(Array<T> &ra, Array<T> &temp, int left, int right);

/*****************************************************************************
* Function: MergeSort
* Parameters:
*        Array<T> &ra
*
* Return: 
*        none
*
* Calls:
*        MergeSortRec - Recursive part of sort
*
* Purpose:
*        Ascending sort of a templated Array.  Fast.
*****************************************************************************/
template <typename T>
void MergeSort(Array<T> &ra)
{
   int size = ra.Size();
   Array<T> temp = ra;

   MergeSortRec(ra, temp, 0, size-1);
}


/*****************************************************************************
* Function: MergeSortRec
* Parameters:
*        Array<T> &ra        - array to be sorted
*        Array<T> &temp        - copy of array - temp working area
*        int left                - left half starting element
*        int right                - right half starting element
*
* Return: 
*        none
*
* Calls:
*        Merge - Merge the two sub-halves together
*
* Purpose:
*        Recursive part of sort
*****************************************************************************/
template <typename T>
void MergeSortRec(Array<T> &ra, Array<T> &temp, int left, int right)
{
        if(left < right)
        {
                int mid = (left+right)/2;
                
                MergeSortRec(ra, temp, left, mid);//left half
                MergeSortRec(ra, temp, mid+1, right);//right half
                Merge(ra, temp, left, mid+1, right);//Merge the halves
        }
}

/*****************************************************************************
* Function: Merge
* Parameters:
*        Array<T> &ra        - array to be sorted
*        Array<T> &temp        - copy of array - temp working area
*        int left                - left half starting element
*        int right                - right half starting element
*        int right_end        - end of right half
*
* Return: 
*        none
*
* Calls:
*        none
*
* Purpose:
*        Merge the two sub-halves together
*****************************************************************************/
template <typename T>
void Merge(Array<T> &ra, Array<T> &temp, int left, int right, int right_end)
{
        int left_end = right-1;
        int temp_pos = left;
        int num_elements = right_end - left+1;
        int start = left;

        while( (left <= left_end) && (right <= right_end) )
        {
                if(ra[left] <= ra[right])
                {
                        temp[temp_pos] = ra[left];
                        temp_pos++;
                        left++;
                }
                else
                {
                        temp[temp_pos] = ra[right];
                        temp_pos++;
                        right++;
                }
        }
        //        Copy the rest of the left array into the temp array
        while(left <= left_end)
        {
                temp[temp_pos] = ra[left];
                temp_pos++;
                left++;
        }
        
        //        Copy the rest of the right array into the temp array
        while(right <= right_end)
        {
                temp[temp_pos] = ra[right];
                temp_pos++;
                right++;        
        }
        //        Copy the temp array over the top of the original array
        for(int i=start ; i<temp_pos ; i++)
                ra[i] = temp[i];
}