/*
   John W. Clark
   This is the merge sort code from class,
   as well as the dummy array version we talked about.
   I also included the macros that use the size instead of the range.
   The print function was added also
 */
#include<iostream.h>

// macros for merge sort, the eliminates the start stop points
// arguements are the array, and the number of elements to sort
#define MERGE_SORT( x , y ) merge_sort( x, 0, ( y - 1 ) )
#define MERGE_SORT2( x , t, y ) merge_sort2( x, t, 0, ( y - 1 ) )

void merge_sort( int arr[], int start, int stop );
void merge_sort2( int arr[], int tmp[], int start, int stop );
void swap ( int & x, int & y );
void print( int arr[], int size );

int main()
{
    {
        // the one we did in class
        int arr[7] = { 6,2,3,5,1,4,7 };
        print ( arr, 7 ) ;
        MERGE_SORT( arr, 7 );
        print ( arr, 7 ) ;
    }
    {
        // test the other version of merge sort
        int arr[7] = { 6,2,3,5,1,4,7 };
        int tmp[7];
        print ( arr, 7 ) ;
        MERGE_SORT2( arr, tmp, 7 );
        print ( arr, 7 ) ;
    }

    return 0;
}

/* =======================================
   void merge_sort( int arr[], int start, int stop )
   input - an array and the index range to sort
   output -
   return - ( by reference ) the sorted array
   notes - this one uses dynamic memory for the left side
   on the merge, which is pretty slow
   ======================================= */
void merge_sort( int arr[], int start, int stop )
{
    int count = stop - start + 1;
    if ( count == 2 )
    {
        if ( arr[ start ] > arr[ stop ] )
            swap( arr[ start ], arr[ stop ] );
    }
    else if ( count > 2 )
    {
        int mid = count / 2 + start;
        merge_sort( arr, start, mid );
        merge_sort( arr, mid + 1, stop );
        // we have two sorted subsets
        // make a copy for the left side of the merge
        int tmp_size = mid - start + 1;
        int * tmp = new int[ tmp_size ];
        for( int i = 0 ; i < tmp_size ; ++i )
            tmp[i] = arr[ i + start ];
        // indexes for the merge
        int left = 0;
        int right = mid + 1;
        int dest = start;
        for( int i = 0 ; i < count ; ++i )
        {
            if ( right > stop )
            {
                // the right side is out of data
                arr[ dest++ ] = tmp[ left++ ];
            }
            else if ( left > ( tmp_size - 1 ) )
            {
                // the left side is out of data
                i = count;  // we are done
            }
            else
            {
                // there is data in both
                // we want to compare elements at tmp[left] and arr[right]
                if ( tmp[left] < arr[right] )
                {
                    // get the left element
                    arr[ dest++ ] = tmp[ left++ ];
                }
                else
                {
                    // get the right element
                    arr[ dest++ ] = arr[ right++ ];
                }
            }
        }
        delete [] tmp;
    }
}

/* =======================================
   void merge_sort2( int arr[], int tmp[], int start, int stop )
   input - an array, a dummy array, and the index range to sort
   output -
   return - ( by reference ) the sorted array
   notes - this one doesn't use dynamic memory, it uses a dummy
   array the same size as the base input array as workspace
   ======================================= */
void merge_sort2( int arr[], int tmp[], int start, int stop )
{
    int count = stop - start + 1;
    if ( count == 2 )
    {
        if ( arr[ start ] > arr[ stop ] )
            swap( arr[ start ], arr[ stop ] );
    }
    else if ( count > 2 )
    {
        int mid = count / 2 + start;
        merge_sort( arr, start, mid );
        merge_sort( arr, mid + 1, stop );
        // copy the left side data into the dummy array
        for( int i = start ; i <= mid ; ++i )
            tmp[ i ] = arr[ i ];
        // indexes for the merge
        int left = start;       // range is start to mid
        int right = mid + 1;    // range is mid + 1 to stop
        int dest = start;
        for( int i = 0 ; i < count ; ++i )
        {
            if ( right > stop )
            {
                // the right side is out of data
                arr[ dest++ ] = tmp[ left++ ];
            }
            else if ( left > mid )
            {
                // the left side is out of data
                i = count;  // we are done
            }
            else// there is data in both
            {
                // we want to compare elements at tmp[left] and arr[right]
                if ( tmp[left] < arr[right] )
                {
                    // get the left element
                    arr[ dest++ ] = tmp[ left++ ];
                }
                else
                {
                    // get the right element
                    arr[ dest++ ] = arr[ right++ ];
                }
            }
        }
    }
}

/* =======================================
   void swap ( int & x, int & y )
   input - two integers, passed by reference
   output -
   return - ( by reference ) the integers will trade values
   ======================================= */
void swap ( int & x, int & y )
{
    int tmp = x;
    x = y;
    y = tmp;
}

/* =======================================
   void print( int arr[], int size )
   input - an array and the size of the array
   output - the array to stdout, elements seperated by spaces
   return - none
   ======================================= */
void print( int arr[], int size )
{
    for( int i = 0 ; i < size ; ++i )
        cout << arr[i] << " ";
    cout << endl;
}