public class QuickSort
{
  
  public static void quickSort(int array[], int lower, int upper)
  {
    // BASE CASE: lower is at or beyond upper, nothing left to sort
    if (lower >= upper)
    {
      return;
    }
    // RECURSIVE CASE: lower is below upper, sort this section of array
    else 
    {
      // Partition array around array[lower].
      int position = partition(array, lower, upper);
      
      // All elements from array[lower} to array[position]
      // are less than or equal to array[position].  Sort 'em
      quickSort(array, lower, position);
      
      // All element from array[position+1] to array[upper]
      // are greater than array[position].  Sort 'em.
      quickSort(array, position+1, upper);
    }
  }
  
// Precondition:  provide array[] an array of items in any order
//                lower is the lower bounds of the array to partition
//                upper is the upper bounds of the array to partition
//
// Postcondition: returns array[] with items partitioned which means:
//     1) pivot is determined (it is always array[0])
//                  2) all items LESS THAN OR EQUAL TO pivot are moved to left of pivot
//                  3) all items GREATER THAN pivot are moved to the right of pivot
//                  4) function returns array index of pivot
//
// EXAMPLE:
//     Start Array: 34 12 24 100 77
//                  Pivot is array[0] = 34
//                  End Array:   24 12 34 100 77
//                  Return, 2, the array index of pivot 
  public static int partition(int array[], int lower, int upper)
  {
    // Get the pivot item.  It's always the first element in
    // the section of the array that we're supposed parition.
    //
    // When we're done with this function, this array section bounded 
    // by upper and lower will be paritioned as follows:
    //    1) all elements <= pivot will be to the LEFT of pivot 
    //    2) all elements > pivot will be to the RIGHT of pivot 
    int pivot = array[lower];
    int left   = lower;
    int right  = upper;
    
    while (true)
    {
      
      // Scan array section from RIGHT to LEFT looking for an
      // element that should be to the left of pivot.  When we're
      // done with this loop, right will be the location of:
      //    1) element that should be to the left of pivot
      //    2) pivot itself
      while ((left < right) && (pivot <= array[right]))
      {
        right--;
      }
      
      // Scan array section from LEFT to RIGHT looking for an
      // element that should be to the RIGHT of pivot.  When we're
      // done with this loop, left will be the location of:
      //   1) element that should be to the right of pivot
      //   2) bogus (if left crosses right)
      while ((left < right) && (pivot >= array[left]))
      {
        left++;
      } 
      
      // (left < right) means we haven't checked every element in array section
      // against the pivot.  It also means that we have two elements that need
      // to be rearranged:
      //
      //    array[left]  needs to be moved to the RIGHT of pivot
      //    array[right] needs to be moved to the LEFT of pivot
      //
      // We can do this very nicely by simply SWAPPING the two elements.
      if(left < right) {
        int temp = array[right];
        array[right] = array[left];
        array[left] = temp;
      }
      
      // (left >= right) means we've scanned the entire array section and 
      // properly positioned the elements with respect to pivot with one exception.
      // We need to get the pivot at array[lower] to its proper location which
      // is array[right].  "right" always works out to be the location of the 
      // pivot element in the array.
      else
      {
        // Move pivot to its proper location in the array
        int position = right;
        array[lower]=array[position];
        array[position]=pivot;
        
        // Return pivot's position
        return position;
      }
    }
  }
  
  public static void main(String[] args)
  {
    int[] array={6,5,9,12,3,4};
    
    quickSort(array,0,5);
    
    for (int i=0; i<6; i++)
    {
      System.out.print(array[i]+" ");
    }
    System.out.println();
  }
}