Quadratic time to sort in a simple case?

[bearophile]

Andrei Alexandrescu:

> c) add introspection to the algorithm, i.e. if an attempt to 
> partition hits the worst case or near worst case, just try 
> another pivot instead of moving forward with the sorting stage.

Or switch to a sort that is guaranteed to have a pseudo-linear 
complexity.
I am not sure, but I think the C++ STL sort does this.


> TimSort is slower on average.

Here it's not easy to define what "average" is. Python devs think 
that a common case is an array with mostly sorted data with 
unsorted data at the end.

Bye,
bearophile