MergeSort

MergeSort.cpp

#include <iostream>
using namespace std;

typedef int DataType;

void merge( DataType theArray[], int first, int mid, int last );
void mergeSort( DataType theArray[], int first, int last );
void displayArray( const DataType theArray[], int first, int last );

const int N_ITEMS = 10;

int main()
{

   DataType a[ N_ITEMS ] = { 10, 5, 21, 5, 99, 8, 16, 4, 72, 25 };

   cout << "Initial array : ";
   displayArray( a, 0, N_ITEMS - 1 );
   cout << endl;

   mergeSort( a, 0, N_ITEMS - 1 );

   cout << "Sorted array : ";
   displayArray( a, 0, N_ITEMS - 1 );
   cout << endl;

   return 0;
}



/** Merges two sorted array segments theArray[first..mid] and
 *  theArray[mid+1..last] into one sorted array.
 * @pre first <= mid <= last. The subarrays theArray[first..mid]
 * and theArray[mid+1..last] are each sorted in increasing order.
 * @post theArray[first..last] is sorted.
 * @param theArray  The given array.
 * @param first  The beginning of the first segment in theArray.
 * @param mid  The end of the first segement in theArray.  mid + 1
 *        marks the beginning of the second segment.
 * @param last  The last element in the second segment in theArray.
 * @note This function merges the two subarrays into a temporary
 * array and copies the result into the original array theArray. */
void merge(DataType theArray[], int first, int mid, int last )
{
   DataType tempArray[N_ITEMS];    // temporary array

   // initialize the local indexes to indicate the subarrays
   int first1 = first;       // beginning of first subarray
   int last1  = mid;         // end of first subarray
   int first2 = mid + 1;     // beginning of second subarray
   int last2  = last;        // end of second subarray

   // while both subarrays are not empty, copy the
   // smaller item into the temporary array
   int index = first1;    // next available location in
                          // tempArray
   for (; (first1 <= last1) && (first2 <= last2); ++index)
   {
      if (theArray[first1] < theArray[first2])
      {  tempArray[index] = theArray[first1];
         ++first1;
      }
      else
      {  tempArray[index] = theArray[first2];
         ++first2;
      }
   }

   // finish off the nonempty subarray

   // finish off the first subarray, if necessary
   for (; first1 <= last1; ++first1, ++index)
   {
      tempArray[index] = theArray[first1];
   }

   // finish off the second subarray, if necessary
   for (; first2 <= last2; ++first2, ++index)
   {
      tempArray[index] = theArray[first2];
   }

   // copy the result back into the original array
   for (index = first; index <= last; ++index)
      theArray[index] = tempArray[index];
}

/** Sorts the items in an array into ascending order.
 * @pre theArray[first..last] is an array.
 * @post theArray[first..last] is sorted in ascending order.
 * @param theArray  The given array.
 * @param first  The first element to consider in theArray.
 * @param last  The last element to consider in theArray. */
void mergeSort(DataType theArray[], int first, int last)
{
   if (first < last)
   {

      int mid = (first + last)/2;    // index of midpoint

      cout << "Sorting left half ---> ";
      displayArray( theArray, first, mid );
      cout << endl;
      // sort left half theArray[first..mid]
      mergeSort( theArray, first, mid );


      cout << "Sorting right half ---> ";
      displayArray( theArray, mid + 1, mid );
      cout << endl;
      // sort right half theArray[mid+1..last]
      mergeSort( theArray, mid + 1, last );


      cout << "Merging two halves ---> ";
      displayArray( theArray, first, last );
      cout << endl;
      // merge the two halves
      merge( theArray, first, mid, last );
   }
}



void displayArray( const DataType theArray[], int first, int last )
{
   for ( int i = first; i <= last; ++i )
   {
      cout << theArray[ i ] << " ";
   }
}