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

Note that the partitioning algorithm requires no extra memory and that
each element is compared exactly once with the pivot. When the code is writ-
ten, this approach translates to a very tight inner loop.

8.6.5 keys equal to the pivot

One important detail that we must consider is how to handle keys that are
equal to the pivot. Should i stop when it encounters a key equal to the pivot,
and should j stop when it encounters a key equal to the pivot? Counters i and
j should do the same thing; otherwise, the partitioning step is biased. For
instance, if i stops and j does not, all keys that are equal to the pivot wind up
on the right-hand side.
Let us consider the case in which all elements in the array are identical. If
both i and j stop, many swaps will occur between identical elements. Although
these actions seem useless, the positive effect is that i and j cross in the mid-
dle, so when the pivot is replaced the partition creates two nearly equal subsets.
Thus the best-case analysis applies, and the running time is O ( N log N ).
If neither i nor j stops, then i winds up at the last position (assuming of
course that it does stop at the boundary), and no swaps are performed. This
result seems great until we realize that the pivot is then placed as the last ele-
ment because that is the last cell that i touches. The result is widely uneven
subsets and a running time that matches the worst-case bound of O ( N 2 ). The
effect is the same as using the first element as a pivot for presorted input: It
takes quadratic time to do nothing.

We conclude that doing the unnecessary swaps and creating even subsets
is better than risking widely uneven subsets. Therefore we have both i and j
stop if they encounter an element equal to the pivot. This action turns out to be
the only one of the four possibilities that does not take quadratic time for this
input.
At first glance, worrying about an array of identical elements may seem
silly. After all, why would anyone want to sort 5,000 identical elements?
However, recall that quicksort is recursive. Suppose that there are 100,000
elements, of which 5,000 are identical. Eventually quicksort could make the
recursive call on only the 5,000 identical elements. Then, ensuring that 5,000
identical elements can be sorted efficiently really is important.

Counters i and j
must stop when
they encounter an
item equal to the
pivot to guarantee
good performance.

8.6.6 median-of-three partitioning

When we do median-of-three partitioning, we can do a simple optimization
that saves a few comparisons and also greatly simplifies the code. Figure 8.19
shows the original array.