// FILE: merge.cpp from Main and Savitch. Modified by Rick Wagner
// November 16, 1999.
// An interactive test program for two mergesort functions

#include <iostream.h>  // Provides cout and cin
#include <stdlib.h>    // Provides EXIT_SUCCESS, size_t

// Turn these functions in function templates for more general use.
// Any objects sorted will need to have overloaded comparison operators:

// PROTOTYPES of the functions used in this test program:
void mergesort(int data[ ], size_t n);
// Precondition: data is an array with at least n components.
// Postcondition: The elements of data have been rearranged so
// that data[0] <= data[1] <= ... <= data[n - 1].
// NOTE: If there is insufficient dynamic memory, then new_handler is called.

void merge(int data[ ], size_t n1, size_t n2);
// Precondition: data is an array (or subarray) with at least n1 + n2 elements. 
// The first n1 elements (from data[0] to data[n1 - 1]) are sorted from smallest 
// to largest, and the last n2 (from data[n1] to data[n1 + n2 - 1]) are also 
// sorted from smallest to largest.
// Postcondition: The first n1 + n2 elements of data have been
// rearranged to be sorted from smallest to largest.
// NOTE: If there is insufficient dynamic memory, then new_handler is called.

void mergeSort(int arrayA[], int arrayB[], int l, int r);
// Precondition: data are in an array with at least r elements.
// Postcondition: The elements of data have been rearranged so
// that data[0] <= data[1] <= ... <= data[r].


int main( )
{
    int iCond = 1;                 // Condition for choosing which merge sort.
    const char BLANK = ' ';
    const size_t ARRAY_SIZE = 100; // Number of elements in the array to be sorted
    int data[ARRAY_SIZE];          // Array of integers to be sorted
    int temp[ARRAY_SIZE];          // Temporary array for Sedgewick's mergeSort();
    int user_input;                // Number typed by the user
    size_t number_of_elements;     // How much of the array is used
    size_t i;                      // Array index

    // Provide some instructions
    cout << "Which merge sort: Main and Savitch or Sedgewick (0, 1)? ";
    cin >> iCond;

    cout << endl << endl << "Please type up to " << ARRAY_SIZE << " positive integers. ";
    cout << "Indicate the list's end with a zero." << endl;

    // Read the input numbers
    number_of_elements = 0;
    cin >> user_input;
    while ((user_input != 0) && (number_of_elements < ARRAY_SIZE))
    {
        data[number_of_elements] = user_input;
        number_of_elements++;
        cin >> user_input;
    }

    // Sort the numbers and print the result with two blanks after each number
    if (iCond)
    {
      mergesort(data, number_of_elements);
    }
    else
    {
      mergeSort(data, temp, 0, number_of_elements - 1);
    }
    cout << "In sorted order, your numbers are: " << endl;
    for (i = 0; i < number_of_elements; i++)
        cout << data[i] << BLANK << BLANK;
    cout << endl;

    return EXIT_SUCCESS;
}

void mergesort(int data[ ], size_t n)
// Precondition: data is an array with at least n components.
// Postcondition: The elements of data have been rearranged so
// that data[0] <= data[1] <= ... <= data[n-1].
// NOTE: If there is insufficient dynamic memory, then new_handler is called.
// Library facilities used: stdlib.h
{
    size_t n1; // Size of the first subarray
    size_t n2; // Size of the second subarray

    if (n > 1)
    {
        // Compute sizes of the subarrays
        n1 = n / 2;
        n2 = n - n1;

        mergesort(data, n1);         // Sort from data[0] through data[n1-1]
        mergesort((data + n1), n2);  // Sort from data[n1] to the end

        // Merge the two sorted halves
        merge(data, n1, n2);
    }
}

void merge(int data[ ], size_t n1, size_t n2)
// Precondition: data is an array (or subarray) with at least n1+n2 elements. 
// The first n1 elements (from data[0] to data[n1-1]) are sorted from smallest 
// to largest, and the last n2 (from data[n1] to data[n1+n2-1]) are also 
// sorted from smallest to largest.
// Postcondition: The first n1+n2 elements of data have been
// rearranged to be sorted from smallest to largest.
// NOTE: If there is insufficient dynamic memory, then new_handler is called.
// Library facilities used: stdlib.h
{
    int *temp;          // Points to dynamic array to hold the sorted elements
    size_t copied  = 0; // Number of elements copied from data to temp
    size_t copied1 = 0; // Number copied from the first half of data
    size_t copied2 = 0; // Number copied from the second half of data
    size_t i;           // Array index to copy from temp back into data

    // Allocate memory for the temporary dynamic array
    temp = new int[n1 + n2];

    // Merge elements, copying from two halves of data to the temporary array
    while ((copied1 < n1) && (copied2 < n2))
    {
        if (data[copied1] < (data + n1)[copied2])
            temp[copied++] = data[copied1++];        // Copy from first half
        else
            temp[copied++] = (data + n1)[copied2++]; // Copy from second half
    }

    // Copy any remaining entries in the left and right subarrays
    while (copied1 < n1)
        temp[copied++] = data[copied1++];
    while (copied2 < n2)
        temp[copied++] = (data+n1)[copied2++];

    // Copy from temp back to the data array, and release temp's memory
    for (i = 0; i < n1 + n2; i++)
        data[i] = temp[i];
    delete [ ] temp; 
}

// This version of the merge sort is adapted from Sedgewick's "Algorithms," p. 166:
// Array A is the input array, array B is a temporary storage array.
void mergeSort(int arrayA[], int arrayB[], int l, int r)
{
  int i = 0;                                      // l is the left index of the array
  int j = 0;                                      // r is the right index of the array
  int k = 0;                                      // i, j, and k are loop indices.
  int m = 0;                                      // m is the middle of the array index.
  int iMinI = 0;                                  // For minimal index.
  int iMaxJ = 0;                                  // For maximal index.
  
  if (r - l > 0)                                  // Recursion stop condition.
  {
    m = (r + l) / 2;                              // Integer division to find the middle.
    mergeSort(arrayA, arrayB, l, m);              // Branching recursion,
    mergeSort(arrayA, arrayB, m + 1, r);          // splitting the array (pushed onto runtime stack).

    // Merge the two arrays (popped from runtime stack):
    iMinI = m;
    for (i = m; i >= l; i--)                      // Copy left of A to left of B.
    {
      arrayB[i] = arrayA[i];
      iMinI = i;                                  // Set the min index.
    }
    iMaxJ = m + l;
    for (j = m + 1; j <= r; j++)                  // Copy right of A to right of B in reverse:
    {
      arrayB[r + m + 1 - j] = arrayA[j];
      iMaxJ = j;                                  // Set the max index.
    }
    for (k = l; k <= r; k++)                      // Do the merging.
    {
      if (arrayB[iMinI] < arrayB[iMaxJ])
      {
        arrayA[k] = arrayB[iMinI];
        iMinI++;
      }
      else
      {
        arrayA[k] = arrayB[iMaxJ];
        iMaxJ--;
      }
    }
  }
}