Quadratic time to sort in a simple case?

bearophile bearophileHUGS at lycos.com
Tue Apr 23 07:11:58 PDT 2013


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


More information about the Digitalmars-d-learn mailing list