Sorting algorithms - Data Structures and Problem Solving Using Java - page 378

would generate many calls that have only small subsets. Thus testing the size
of the subset is worthwhile. If it is smaller than some cutoff, we apply inser-
tion sort; otherwise, we use quicksort.
A good cutoff is 10 elements, although any cutoff between 5 and 20 is
likely to produce similar results. The actual best cutoff is machine dependent.
Using a cutoff saves us from degenerate cases. For example, finding the
median of three elements does not make much sense when there are not three
elements.
In the past, many thought that an even better alternative was to leave the
array slightly unsorted by doing absolutely nothing when the subset size was
below the cutoff. Because the insertion sort is so efficient for nearly sorted
arrays, we could show mathematically that running a final insertion sort to
clean up the array was faster than running all the smaller insertion sorts. The
savings were roughly the overhead of the insertion sort method calls.
Now, method calls are not as expensive as they used to be. Furthermore a
second scan of the array for the insertion sort is expensive. Because of a tech-
nique called caching, we are better off doing the insertion sort on the small
arrays. Localized memory accesses are faster than nonlocalized accesses. On
many machines, touching memory twice in one scan is faster than touching
memory once in each of two separate scans.
The idea of combining a second sorting algorithm when recursive calls to
quicksort seem inappropriate can also be used to guarantee an O ( N log N )
worst case for quicksort. In Exercise 8.20 you are asked to explore combining
quicksort and mergesort to get quicksort's average-case performance almost
all the time with mergesort's worst-case guarantee. In practice, instead of
mergesort we use another algorithm, namely heapsort, which we discuss in
Section 21.5.

8.6.8 java quicksort routine

The actual implementation of quicksort is shown in Figure 8.22. The one-
parameter quicksort , declared at lines 4 to 8, is merely a driver that calls the
recursive quicksort . Thus we discuss only the implementation of the recursive
quicksort .
At line 17 we test for small subarrays and call the insertion sort (not
shown) when the problem instance is below some specified value given by the
constant CUTOFF . Otherwise, we proceed with the recursive procedure. Lines 21
to 27 sort the low, middle, and high elements in place. In keeping with our
previous discussion, we use the middle element as the pivot and swap it with
the element in the next-to-last position at lines 30 and 31. We then do the par-
titioning phase. We initialize the counters i and j to 1 past their true initial val-
ues because the prefix increment and decrement operators will immediately

We use a driver to
set things up.