//  Program:  merge sort
//  Author:   Chuck Stewart
//
//  Purpose:  A program to demonstrate the recursive merge sort technique.


#include <iostream>
#include <vector>
using namespace std;

// merge function will merge two sorted intervals of a vector,
//  using "scratch" as temporary copying space
// the intervals are subscript locations low..mid and mid+1..high

// e.g.  2 7 9      3 6 8
//             i          j
//
//                scratch    2 3 6 7 8 9
//                                     k

template <class T>
void
merge( int low, int mid, int high,
       vector<T>& values, vector<T>& scratch )
{
  cout << "merge(): low is " << low << ", mid is " << mid
       << ", and high is " << high << endl;

  int i = low, j = mid + 1, k = low;

  while ( i <= mid && j <= high )
  {
    if ( values[i] < values[j] )
    {
      scratch[k] = values[i];
      k++;
      i++;
    }
    else
    {
      scratch[k] = values[j];
      k++;
      j++;
    }
  }

  // copy over remaining elements of either of the sub-vectors
  //   that we're merging
  while ( i <= mid )  { scratch[k++] = values[i++]; }
  while ( j <= high ) { scratch[k++] = values[j++]; }

  // copy the sorted result from scratch to values
  for ( k = low ; k <= high ; k++ ) {
    values[k] = scratch[k];
  }
}

//  Here's the actual merge sort function.  It splits the vector in
//  half, recursively sorts each half, and then merges the two sorted
//  halves into a single sorted interval.
//
template <class T>
void
mergesort( int low, int high,
           vector<T>& values, vector<T>& scratch )
{
  cout << "mergesort(): low is " << low
       << " and high is " << high << endl;

  if ( low >= high ) {
    // stop the recursion -- i.e. we have a vector of size 0 or 1
    //                            (which are already sorted!)
    return;
  }

  int mid = ( low + high ) / 2;

  // handle the left-hand side of the vector
  mergesort( low, mid, values, scratch );

  // handle the right-hand side of the vector
  mergesort( mid + 1, high, values, scratch );

  // merge the two sub-vectors
  merge( low, mid, high, values, scratch );
}


//  The driver function for mergesort.  It defines a scratch vector
//  for temporary copies.  It passes this vector along with the region
//  to be sorted to the recursive mergesort function.
//
template <class T>
void
mergesort( vector<T>& values )
{
  vector<T> scratch( values.size() );
  mergesort( 0, values.size() - 1, values, scratch );
}


int main()
{
  vector<double> pts( 7 );
  pts[0] = -45.0;  pts[1] =   89.0;  pts[2] =    34.7;  pts[3] =   21.1;
  pts[4] =   5.0;  pts[5] =  -19.0;  pts[6] =  -100.3;  // pts[7] =    3.8;
  // pts[8] =  77.1;  pts[9] =   13.6;  pts[10] = -221.4;  pts[11] = 121.5;
  //  pts[12] = 25.9;  pts[13] = 123.2;  pts[14] =   66.6;  pts[15] =   8.3;
  // pts[16] = 55.5;  pts[17] = 898.1;  pts[18] =   42.3;  pts[19] =  77.7;

  cout << "\nUNSORTED:\n";
  for ( unsigned int i = 0 ; i < pts.size() ; i++ )
    cout << i << ": " << pts[i] << endl;

  mergesort( pts );

  cout << "\nSORTED:\n";
  for ( unsigned int i = 0 ; i < pts.size() ; i++ )
    cout << i << ": " << pts[i] << endl;

  return 0;
}