Fun with fancy slicing

[David Eppstein]

In article <3f7bf423$0$20654$626a54ce at news.free.fr>,
 Damien Wyart <damien.wyart at free.fr> wrote:

> * David Eppstein <eppstein at ics.uci.edu> in comp.lang.python:
> > Of course we know that nonrandom quicksort pivoting can be quadratic
> > anyway (e.g. on sorted input) but this to my mind is worse because
> > randomization doesn't make it any better. The fact that some textbooks
> > (e.g. CLRS!) make this mistake doesn't excuse it either.
> 
> Could you explain in more detail the error made in CLRS on this topic
> (with a reference if possible) ? I did not precisely catch your
> explanation here.
> 
> Thanks in advance,

CLRS' partition routine ends up partitioning an n-item array into the 
items <= the pivot, the pivot itself, and the items > the pivot.
If the items are all equal, that means that the first part gets n-1 
items and the last part gets nothing, regardless of which item you 
select as pivot.  If you analyze the algorithm on this input, you get 
the recurrence T(n)=O(n)+T(n-1)+T(0) which solves to O(n^2).

Throughout most of the quicksort chapter, CLRS at least include 
exercises mentioning the case of all equal inputs, asking what happens 
for those inputs, and in one exercise suggesting a partition routine 
that might partition those inputs more equally (but who knows what it 
should do when merely most of the inputs are equal...)  However in the 
randomized quicksort section they ignored this complication and seemed 
to be claiming that their randomized quicksort has O(n log n) expected 
time, unconditionally.

This problem was finally corrected in the fourth printing of the second 
edition; see the errata at 
<http://www.cs.dartmouth.edu/~thc/clrs-2e-bugs/bugs.php>
for more details.

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science