public class QuickSorter
{
   private int[] a;

   public QuickSorter(int[] anArray)
   {
      a = anArray;
   }   

   /**
      Sorts the array managed by this quick sorter
   */
   public void sort()
   {  
      sort(0, a.length - 1);
   }

   public void sort(int from, int to)
   {
      int[] b = partition(from, to);
      int[] p = moveRegions(from, b[0], b[1], b[2], to);
      sort(from, ...);
      sort(..., to);
   }

   /**
      Partitions the subarray a[from]...a[to] into four regions
      and returns an array containing three boundary positions
      b0 b1 b2. After the call,
      Elements equal to a[from] have positions from...b0
      Elements < a[from] have positions b0+1...b1-1
      Elements > a[from] have positions b1...b2-1
      Elements equal to a[from] have positions b2...to
   */
   public int[] partition(int from, int to)
   {
      int pivot = a[from];
      int i0 = from;    // last index at left == pivot
      int j0 = to + 1;  // first index at right == pivot
      int i = i0 + 1; 
      int j = j0 - 1;  
      while (i <= j)
      {
	 /*
	 |   =   |   <   | ?        ? |   >   |   =  |
               i0          i        j          j0
	 */

	 if (a[i] < pivot)
	 {
	    ...
	 }
	 else if (a[i] == pivot)
	 {
	    ...
	 }
	 else if (a[j] > pivot)
	 {
	    ...
	 }
	 else if (a[j] == pivot)
	 {
	    ...
	 }
	 else // a[i] > pivot and a[j] < pivot
	 {
	    ...
	 }
      }
      /*
        [      =     |   <   |    >   |     =     ]
         from       i0        i       j0         to
       */
      return new int[] { ..., ..., ...};
   }

   /**
      Before the call,
      Elements in positions from...b0 have the same value v
      Elements in positions b0+1...b1-1 have a value < v
      Elements in positions b1...b2-1 have a value > v
      Elements in position b2...to have value v
      The method returns an array with two positions p0 p1.
      After the call,
      Elements in positions from...p0 have a value < v
      Elements in positions p0+1...p1-1 have value v
      Elements in positions p1...to have a value > v
   */
   public int[] moveRegions(int from, int b0, int b1, int b2, int to)
   {
      /*

        [      =     |   <   |    >   |     =     ]
         from       b0       b1       b2         to
       */

      // ...
      return new int[] { ..., ... };
   }

   /**
      Swaps two entries of the array.
      @param i the first position to swap
      @param j the second position to swap
   */
   private void swap(int i, int j)
   {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
   }
}