[graycat]

Right. So, for the first "pivot" value, people commonly use the median of three -- take three keys and use as the pivot the median of those three, that is, the middle value. Okay. But then the question remains: While in practice the median of three sounds better, maybe there is a goofy, pathological array of keys that still makes quicksort run in quadratic time. Indeed, maybe for any way of selecting the first pivot, there is an array that makes quicksort quadratic.

Rather than think about that, I noticed that heap sort meets the Gleason bound which means that heap sort's O(n ln)n)) performance both worst case and average case can never be beaten by a sort routine that depends on comparing keys two at a time.

Then, sure, can beat O(n ln(n)). How? Use radix sort -- that was how the old punched card sorting machines worked. So, for an array of length n and a key of length k, the thing always runs in O(nk) which for sufficiently large n is less than O(n ln(n)). In practice? Nope: I don't use radix sort!