//
//  File: quick.h
//
//   This is the enhanced version of quick sort with median of 3
//   pivoting and use of insertion sort for small sublists.
// 

const int Cutoff = 14;   // sublists with Cutoff or fewer elements are
			 // sorted using insertion sort


template <class T>
inline void
Swap( T & A, T & B )
{
  T Tmp = A;
  A = B;
  B = Tmp;
}


//  Return the median of A[Left], A[Center] and A[Right].  Leave the
//  smallest value in A[Left], the largest value in A[Right] and the
//  median value in A[Right-1].
//
template <class T>
T &
Median3( T A[ ], int Left, int Right )
{
  unsigned int Center = ( Left + Right ) /2;

  if( A[ Left ] > A[ Center ] )
    Swap( A[ Left ], A[ Center ] );
  if( A[ Left ] > A[ Right ] )
    Swap( A[ Left ], A[ Right ] );
  if( A[ Center ] > A[ Right ] )
    Swap( A[ Center ], A[ Right ] );

  // Result: A[ Left ] <= A[ Center ] <= A[ Right ].
  // Now shift pivot to position Right-1 and return the pivot.

  Swap( A[ Center ], A[ Right - 1 ] );
  return A[ Right - 1 ];
}


template <class T>
void
Q_Sort( T A[ ], int Left, int Right )
{
  if( Left + Cutoff <= Right ) {
    T Pivot = Median3( A, Left, Right );
    unsigned int i = Left, j = Right - 1;

    for( ; ; ) {
      while( A[ ++i ] < Pivot );
      while( A[ --j ] > Pivot );
      if( i < j )
	Swap( A[ i ], A[ j ] );
      else
	break;
    }

    //  Place the pivot in its correct position.  Note that this
    //  position is A[i].  In the basic version it was A[ j ].
    //  Can you figure out why?
    //
    Swap( A[ i ], A[ Right-1 ] );

    Q_Sort( A, Left, i-1 );
    Q_Sort( A, i+1, Right );
  }
}

// templates for the main sort function called by the Quick_Sort
// driver function.


template <class T>
void
Quick_Sort( T A[ ], int N )
{
  Q_Sort( A, 0, N-1 );
  Insertion_Sort( A, N );
}