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