//
//  File:  insert.h
//
//  Code for insertion sort

template <class T>
void
Insertion_Sort( T A[ ], int N )
{
  T tmp;

  for( int i = 1; i < N; i++ ) {
    tmp = A[ i ];
    int j = i-1;
    while ( j >= 0 && tmp < A[ j ] ) {
      A[ j+1 ] = A[ j ];
      -- j;
    }
    A[ j+1 ] = tmp;
  }
}


//
//  File: mergesort.h
//

template <class T>
void MergeSort( T A[], int n )
{
  MergeSort( A, 0, n-1 );
}

template <class T>
void MergeSort( T A[], int low, int high )
{
  if ( low == high ) return;
  
  int mid = (low + high) / 2;
  MergeSort( A, low, mid );
  MergeSort( A, mid+1, high );

  //  At this point the lower and upper halves
  //  of "A" are sorted. All that remains is
  //  to merge them into a single sorted list.

  T* temp = new T[high-low+1];  // scratch array for merging
  int i=low, j=mid+1, loc=0;
  
  //  while neither the left nor the right half is exhausted, 
  //  take the next smallest value into the temp array
  while ( i<=mid && j<=high ) {
    if ( A[i] < A[j] ) temp[loc++] = A[i++];
    else                   temp[loc++] = A[j++];
  }

  //  copy the remaining values --- only one of these will iterate
  for ( ; i<=mid; i++, loc++ ) temp[loc] = A[i];
  for ( ; j<=high; j++, loc++ ) temp[loc] = A[j];

  //  copy back from the temp array
  for ( loc=0, i=low; i<=high; loc++, i++ ) A[i]=temp[loc];
  delete [] temp;

}



//
//  File:  heap.h
//
//  Sorts by building a max heap, then continually removing the
//  maximum remaining element to its proper place and reducing the
//  size of the heap.
//
//  There is one important note about this code.  Since the array A
//  starts at 0 instead of the usual 1 for a heap, the children of
//  each heap node i are in locations 2i+1 and 2i+2 and the last
//  non-leaf value is in location floor(N/2)-1. 

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

template <class T>
void
Percolate_Down( T A[], int i,  int N )
{
  int child;
  T tmp = A[ i ];

  for( ; i*2+1 < N; i = child ) {
    child = i*2+1;
    if ( child != N-1 && A[ child+1 ] > A[ child ] ) child++;
    if( tmp < A[ child ] )
      A[ i ] = A[ child ];
    else
      break;
  }
  A[ i ] = tmp;
}


template <class T>
void
Heap_Sort( T A[],  int N )
{
  int i;
  for( i = N/2-1; i >= 0; i-- )   // Build_Heap.
    Percolate_Down( A, i, N );

  for( i = N-1; i >= 1; i-- ) {
    Swap( A[ 0 ], A[ i ] ); // Delete_Max.
    Percolate_Down( A, 0, i );
  }
}

//
//  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.
//

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

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 );
}