Go rant

bearophile bearophileHUGS at lycos.com
Wed Dec 30 11:57:25 PST 2009


Don:
> It'd be interesting to know how the two-pivot quicksort compares to timsort.

Timsort is probably a bit slower, but they can't be compared, because Timsort is a stable sort, while normal quicksorts aren't.


> I suspect there's a median-of-five-killer worst case for this quicksort, 
> just as there's a median-of-three killer for standard quicksort.

Yes, there is. The purpose of using two pivots is not to avoid the inevitable worst case (that's made of usually a limited number of permutations, where the really worst is just one specific permutation), but to avoid a whole class of worst cases, where items are distributed in few equivalence classes. This case is much more common, it's not a sharp point in the landscape of the possible input permutations, it's a plateu, so it deserves to be fixed, and there's a simple way to fix it.

In practice the presence of the O(n^2) sharp worst case is worrying enough the Java devs, so in Java the quicksort is used only for native data. On classes it uses a safer sorting routine not-quicksort based, so a possible attacker can't put inside the class some logic to dynamically find the worst case and attack a Java system.

I think the default system sort of a language like D has to be stable (as in Python), and the unstable algorithm (a templated introsort based on 2 pivot quicksort, with 1 recursive call, trimedian of trimedian, with fallback on heapsort in slow situations) can be used just as optimization when necessary.

I don't know if the safety adopted by Java (to not use quicksort on objects) is a good idea in D2 too.

Bye,
bearophile



More information about the Digitalmars-d mailing list