Source of 9.18.java

Structures and functions

  1: /** Sorts an array into ascending order. Uses quick sort with
  2:     median-of-three pivot selection for arrays of at least 
  3:     MIN_SIZE entries, and uses insertion sort for other arrays. */
  4: public static <T extends Comparable<? super T>>
  5:        void quickSort(T[] a, int first, int last)
  6: {
  7:    if (last - first + 1 < MIN_SIZE)
  8:    {
  9:       insertionSort(a, first, last);
 10:    }
 11:    else
 12:    {
 13:       // Create the partition: Smaller | Pivot | Larger
 14:       int pivotIndex = partition(a, first, last);
 15: 
 16:       // Sort subarrays Smaller and Larger
 17:       quickSort(a, first, pivotIndex - 1);
 18:       quickSort(a, pivotIndex + 1, last);
 19:    } // end if
 20: } // end quickSort
 21: // Version 4.0