//
//  File:  basic_quick.h
//
//    This is the basic version of the quicksort algorithm, with the
//    Left element used as the pivot at all times and no use of
//    insertion sort for small intervals.  Note that the first while
//    loop includes a test to see if i has gone out of range.  This
//    would occur if the pivot were the smallest element in the
//    interval from Left to Right.
//
//    The function "Swap" is in "quick.h"


template <class T>
void
B_Q_Sort( T A[ ], int Left, int Right )
{
  if ( Left >= Right ) return;

  T Pivot = A[ Left ];
  unsigned int i = Left, j = Right+1;

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

  Swap( A[ j ], A[ Left ] ); // Place the pivot in its final position

  B_Q_Sort( A, Left, j - 1 );
  B_Q_Sort( A, j + 1, Right );
}

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