/* Filename:  msort.cpp

   Author:  Br. David Carlson

   Date:  April 26, 1998

   This file contains the implementation of the MergeSort function
   prototypes in msort.h.
*/

#include "msort.h"


/* Given:  NumArray  Array of ints.
           Lower     An index into the array.
           Upper     An index into the array.
   Task:   To quicksort the section of the array from index Lower to Upper.
   Return: NumArray  The sorted array.
*/
void MergeSort(IntArray NumArray, int Lower, int Upper)
   {
   IntArray TempArray;
   int k, Mid;

   if (Lower < Upper)   // if not we have a stopping case
      {
      Mid = (Lower + Upper - 1) / 2;
      MergeSort(NumArray, Lower, Mid);      // recursive call
      MergeSort(NumArray, Mid + 1, Upper);  // recursive call

      // Merge the two sorted pieces together:
      Merge(TempArray, NumArray, NumArray, Lower, Upper,
         Lower, Mid, Mid + 1, Upper);

      // Copy the data back into NumArray:
      for (k = Lower; k <= Upper; k++)
         NumArray[k] = TempArray[k];
      }
   }


/* Given:  LeftArray    Sorted array of ints.
           RightArray   Sorted array of ints.
           LeftLower    An index into LeftArray.
           LeftUpper    An index into LeftArray.
           RightLower   An index into RightArray.
           RightUpper   An index into RightArray.
           OutLower     An index into OutArray.
           OutUpper     An index into OutArray.
   Task:   To merge the section of LeftArray from LeftLower to LeftUpper
           with the section of RightArray from RightLower to RightUpper,
           sending the sorted data into OutArray, from OutLower to
           OutUpper.
   Return: OutArray     Containing the sorted data, from OutLower to
                        OutUpper.
*/
void Merge(IntArray OutArray, IntArray LeftArray, IntArray RightArray,
   int OutLower, int OutUpper,
   int LeftLower, int LeftUpper,
   int RightLower, int RightUpper)
   {
   bool CopyLeft;
   int LeftIndex, RightIndex, OutIndex;

   LeftIndex = LeftLower;
   RightIndex = RightLower;
   OutIndex = OutLower;

   while (OutIndex <= OutUpper)
      {
      // Determine whether to copy from LeftArray:
      if (RightIndex > RightUpper)
         CopyLeft = true;
      else if (LeftIndex > LeftUpper)
         CopyLeft = false;
      else
         CopyLeft = (LeftArray[LeftIndex] < RightArray[RightIndex]);

      // Copy from LeftArray or RightArray as indicated by CopyLeft:
      if (CopyLeft)
         {
         OutArray[OutIndex] = LeftArray[LeftIndex];
         LeftIndex++;
         }
      else   // Copy from RightArray:
         {
         OutArray[OutIndex] = RightArray[RightIndex];
         RightIndex++;
         }

      OutIndex++;
      }
   }