On Tuesday, 23 April 2013 at 17:42:08 UTC, Xinok wrote:
Choosing a random pivot will always invoke "average"
performance where as finding the median of N elements usually
achieves better performance on sorted lists. You also have to
be careful that equal elements are distributed equally among
both partitions, else a list with many elements equal to the
pivot will still achieve poor performance. (equal elements
would all fall onto one side of the pivot)
Introsort is simply a quick sort which falls back to a heap
sort after so many recursions to guarantee O(n log n)
performance. I've implemented this using a median of five and
it works excellent. This is what I plan to contribute to Phobos.
I like the sound of that!
Regarding my previous post, it's perhaps worth mentioning Go in
the comparison, it uses QuickSort with median-of-three for small
sizes and median of medians-of-three for larger sizes [1]. And
it actually sorts the three medians in median-of-three, which
sounds like a good thing to do. They cite "Engineering a Sort
Function" (1993) by Bentley and McIlroy as inspiration [2].
Ivan Kazmenko.
-----
[1] http://golang.org/src/pkg/sort/sort.go#L104
[2]
http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/421/09/bentley93engineering.pdf
