Re: [boost] [sorting] Taking away quicksort and mergesort

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 
cache.

> 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. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo