Recursion - Multimedia Introduction to Programming Using Java - page 413

the segment using partition(b, h, k) produces an array segment that looks
like this:

h j k
≤ b[j] ≥ b[j]

In this situation, what remains to be done? Well, segment b[h.. j -1] has to be
sorted and segment b[j+1..k] has to be sorted. Once they are in non-descend-
ing order, the complete segment b[h..k] is in non-descending order. So that is
it! The complete basic quicksort is given in Fig. 15.8.

15.4.3 Quicksort at its best

Figure 15.9 contains procedure quicksort with one change. The base case
occurs when the segment to be sorted has less than 2 elements, rather than 10 , so
that we can analyze quicksort on a small, 16-element array segment:

Activity
15-4.2

/** Sort b[h..k] */
public static void quicksort( int [] b, int h, int k) {
if (k+1-h < 10) {
insertionsort(b, h, k);
return ;

}

int j= partition(b, h, k);
// { b[h..j-1] <= b[j] <= b[j+1..k] }
quicksort(b, h, j - 1);
quicksort(b, j + 1, k);

}

Figure 15.8: Basic quicksort

/** Sort b[h..k] */
public static void quicksort( int [] b, int h, int k) {
if (k+1-h<2) {
insertionsort(b, h, k);
return ;

}

int j= partition(b, h, k);
// { b[h..j-1] <= b[j] <= b[j+1..k] }
quicksort(b, h, j - 1);
quicksort(b, j + 1, k);

}

Figure 15.9: Basic quicksort with a base case of a segment with at most one element