Quadratic time to sort in a simple case?

[Xinok]

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)