public class QuickSort
{
   final static int CUTOFF = 20;
/**
 * Public access to straight quick sort
 */
   public static void qSort (Comparable [] x, int n)
   {  qSort (0, n-1, x);  }

/**
 * Public access to optimized quick sort
 */
   public static void qSortO (Comparable [] x, int n)
   {  qSortO(0, n-1, x);  }

/**
 * Straight quick sort --- recurse all the way to segments of size 1
 */
   static void qSort (int lo, int hi, Comparable [] x)
   {/* Basic QuickSort algorithm:

          1)  Check for exit condition:  if hi does not come after lo,
              there is nothing left to sort.
          2)  Let the "partition" function position one element to its
              exact position:  everything to its left belongs on the
              left, everything to its right belongs on its right.
          3)  QuickSort can then call itself to sort everything to the
              left as a sub-array.
          4)  Rather than recursively calling itself for the right
              sub-array, QuickSort can just update lo and stay within
              the current call, thus removing the tail recursion.

       Note:  Almost _all_ of the work for qSort is embedded in the
              partition routine.
   */
      int mid;

      while (lo < hi)   // while allows for removing tail recursion
      {  mid = partition(lo, hi, x);
         qSort(lo, mid - 1, x);   // Recursive part for left
         lo = mid + 1;            // "Tail" recursion on right
      } // end while
   }

/**
 * Optimized quick sort --- insertion sort for segments < CUTOFF
 */
   static void qSortO(int lo, int hi, Comparable [] x)
   {  int mid;

      while (lo < hi)   // while allows for removing tail recursion
      {  if ( hi-lo < CUTOFF )            // Small case: Insert Sort
         {  inSort(lo, hi, x); break;  }

         mid = partition(lo, hi, x);
         qSortO(lo, mid - 1, x);          // Recursive part for left
         lo = mid + 1;                    // "Tail" recursion on right
      } // end while
   }

/**
 * Swap two elements in an array --- used by partition
 */
   static void swap (int lt, int rt, Object [] x)
   {  Object tmp = x[lt];  x[lt] = x[rt];  x[rt] = tmp;  }

/**
 * Partition method used by quick sort methods.
 */
   static int partition (int lo, int hi, Comparable [] x)
   {/*Rearrange the x[] array so that a single element is properly
      positioned:  all elements to the left of the "partitioning
      element" (or pivot) belong on the left; all to the right
      belong on the right.  The position of this partitioning
      element is then the value of the partition function.

      This version of partition based on Thomas Naps, "Introduction
      to Data Structures and Algorithm Analysis"; the Median of Three
      improvement is taken from Robert Sedgewick, "Algorithms."
   */
   // "Median of Three" --- middle element becomes the actual element.
   //                       Insure that ends up in x[lo].
      int mid;
      Comparable hold;

      if (lo >= hi) return hi;
      mid = (lo + hi) / 2;
   // We wish to move the median -- b in "abc" -- to position lo
      if (x[lo].compareTo(x[hi]) < 0)        // abc acb bac
         if (x[lo].compareTo(x[mid]) < 0)    // abc acb
            if (x[mid].compareTo(x[hi]) < 0) // abc
               swap(lo, mid, x);
            else                             // acb
               swap(lo, hi, x);
         else ;                              // bac --- null statement
      else                                   // bca cab cba
         if (x[lo].compareTo(x[mid]) > 0)    // otherwise bca and no action
            if (x[mid].compareTo(x[hi]) > 0) // cba
               swap(lo, mid, x);
            else                             // cab
               swap(lo, hi, x);
   // Open up a "hole" at x[lo], with median as pivot value
      hold = x[lo];
   // The loop has two exits:  the two places where the lo and the hi
   // indexes have come together.  In lieu of extra flags or logical
   // comparisons, this code uses an explicit "break" at those two places.
      while (true)      // Note:  "break" out when (lo == hi)
      {//Search for the value from hi downward to plug the hole at x[lo]
         while (hold.compareTo(x[hi]) < 0 && lo < hi)
            hi = hi - 1;
   //    If we've come together, we're done
         if (lo == hi) break;
   //    Otherwise plug the hole at lo with the value at hi
         x[lo] = x[hi];
   //    The hole is now at hi and lo is guaranteed good w.r.t. Pivot
         lo = lo + 1;

   //    Search for the value from lo upward to plug the hole at x[hi]
         while (x[lo].compareTo(hold) < 0 && lo < hi)
            lo = lo + 1;
   //    If we've come together, we're done
         if (lo == hi) break;
   //    Otherwise plug the hole at hi with the value at lo
         x[hi] = x[lo];
   //    The hole is now at lo and hi is guaranteed good w.r.t. Pivot
         hi = hi - 1;
      } // end "infinite" while loop --- (lo == hi) became true
   // Plug the remaining hole (which is guaranteed to be in hi = lo)
   // with the pivot value, making this the partitioning element.

      x[hi] = hold;

      return hi;
   }

/**
 * Insertion sort method, used by qSortO
 */
   public static void inSort ( int lo, int hi, Comparable[] x )
   {  int  lim,    // start of unsorted region
           hole;   // insertion point in sorted region

      for ( lim = lo+1 ; lim <= hi ; lim++ )
      {  Comparable save = x[lim];

         for ( hole = lim ;
               hole > lo && save.compareTo(x[hole-1]) < 0 ;
               hole-- )
         {  x[hole] = x[hole-1];  }

         x[hole] = save;
      } // end for (lim...
   } // end inSort()
}