That's usually called Introsort, but I think you'll find that most of these still consider at least the middle element for a pivot, so they still have a more co

That's usually called Introsort, but I think you'll find that most of these still consider at least the middle element for a pivot, so they still have a more complex cache behaviour than the naïve linear sweep from both ends of a simple Quicksort. https://en.wikipedia.org/wiki/Introsort#Implementations https://en.wikipedia.org/wiki/Introsort#Implementations And heapsort has terrible cache behaviour.