On Tuesday, 23 April 2013 at 14:12:01 UTC, bearophile wrote:
Andrei Alexandrescu:
There's not "the C++ STL sort". Any implementation is fine as
long as it has O(n log n) expected run time.
This seems to use the Introsort:
http://www.sgi.com/tech/stl/sort.html
I don't know if Xinok has tested a 2-pivot quicksort (called by
the usual Introsort setting).
Bye,
bearophile
On an average case, two-pivot quick sort will increase the number
of comparisons by about 50%, reason being that about half the
elements will be greater than the first pivot and have to he
compared to the second pivot. There's also a greater complexity
given there are three partitions rather than two, increasing the
amount of I/O necessary.
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.
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)
