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
