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

can be faster than mergesort because the partitioning step can be performed
significantly faster than the merging step can. In particular, the partitioning
step can be performed without using an extra array, and the code to implement
it is very compact and efficient. This advantage makes up for the lack of
equally sized subproblems.

8.6.2 analysis of quicksort

The algorithm description leaves several questions unanswered: How do we
choose the pivot? How do we perform the partition? What do we do if we see
an element that is equal to the pivot? All these questions can dramatically
affect the running time of the algorithm. We perform an analysis to help us
decide how to implement the unspecified steps in quicksort.

best case

The best case for quicksort is that the pivot partitions the set into two
equally sized subsets and that this partitioning happens at each stage of the
recursion. We then have two half-sized recursive calls plus linear overhead,
which matches the performance of mergesort. The running time for this case
is O ( N log N ) . (We have not actually proved that this is the best case.
Although such a proof is possible, we omit the details here.)

The best case
occurs when the
partition always
splits into equal
subsets. The run-
ning time is
O ( N log N ) .

worst case

Since equally sized subsets are good for quicksort, you might expect that
unequally sized subsets are bad. That indeed is the case. Let us suppose
that, in each step of the recursion, the pivot happens to be the smallest ele-
ment. Then the set of small elements L will be empty, and the set of large
elements R will have all the elements except the pivot. We then have to
recursively call quicksort on subset R . Suppose also that T ( N ) is the run-
ning time to quicksort N elements and we assume that the time to sort 0 or
1 element is just 1 time unit. Suppose further that we charge N units to
partition a set that contains N elements. Then for N > 1, we obtain a run-
ning time that satisfies

The worst case
occurs when the
partition repeatedly
generates an
empty subset. The
running time is
O ( N 2 ) .

TN () = TN 1 ( - ) + N

(8.1)

In other words, Equation 8.1 states that the time required to quicksort N
items equals the time to sort recursively the N - 1 items in the subset of
larger elements plus the N units of cost to perform the partition. This
assumes that in each step of the iteration we are unfortunate enough to pick
the smallest element as the pivot. To simplify the analysis, we normalize by