Boost logo

Boost :

From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2007-03-18 20:27:54

Herve Bronnimann wrote:
> Rene: you misunderstood the meaning of the word optimal in that
> algorithm.

Perhaps :-) I only found the references I posted today. My original
source for the algo was in a paper for creation of suffix arrays. In my
use case I can't use the standard sort (specifically stable_sort),
because the implementation doesn't provide the appropriate hooks to do
the needed updates on the suffix array build procedure.

> There is no version of quicksort which takes n log n time
> in the worst case, short of doing some selection on the pivot.

Now it's you that has to be clear. Do you mean "short of doing some
selection *of* the pivot"? I ask because the Bentley-McIlroy paper does
use pivot selection. Albeit it's a statistical sampling selection, which
is why it adds to the complexity and it also doesn't play nice with the

> The
> algorithm you quote, iirc, is optimal on average even when the
> distribution has many equal elements (which in itself is an
> achievement since almost any version of quicksort is not going to
> have an average time of n log n when many elements are equal). It can
> still (for some particular sequence) take quadratic time. Doug
> McIlroy gave such a sequence in the 80s (he calls it the killer
> sequence since it makes almost any variation of quicksort run in
> quadratic time).

Hm, I would think McIlroy would take such a sequence into consideration
in the paper he writes, with Bentley, in 93.

> Please, take a look at John Valois revisited
> version of introsort. John no longer works in academia, but at some
> point he posted his code online and I believe it must still be out
> there. It's a good read ! Herve -- Hervé

I'm failing to find a reference to that. Any change you know where to
find it?

...Anyway my original point in this thread was that different sort
implementations offer different trade offs if one has some knowledge
about the input sequences. Hence dismissing them just because they
aren't faster than the standard sort is premature.

-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. -
-- rrivera/ - grafik/
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo

Boost list run by bdawes at, gregod at, cpdaniel at, john at