// qsort2.C
#include "qsort2.h"
#include "partition.h"
#include "swap.h"

// Algorithm: improved quicksort

void Quicksort(int vec[],
               int loBound, int hiBound)
{
  if (hiBound-loBound == 1) { // Two items
    if (vec[loBound] > vec[hiBound]) {
      swap(vec[loBound], vec[hiBound]);
    }
    return;
  }

  int someSub = partition(vec, loBound,
			       hiBound);
  
  if (loBound < someSub-1) {
    // 2 or more items in 1st subvec
    Quicksort(vec, loBound, someSub-1);
  }
  
  if (someSub+1 < hiBound) {
    // 2 or more items in 2nd subvec
    Quicksort(vec, someSub+1, hiBound);
  }
}