Hacker News Reader

In practice, to avoid worse case quadratic time, you have to have a rather involved pivot selection in Quicksort. Eg nine random or evenly distributed elements which you put in three groups of three and take the median of the median.

Collecting those nine elements looks terrible for locality.

Funnelsort is a cache oblivious variant of merge sort which is provably cache optimal in some sense. I haven't tried implementing it.

View on HN

To handle quadratic edge cases you would switch to heapsort when the recursion depth goes above the threshold. I.e. introsort; no need for convoluted pivot selection methods.

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

And heapsort has terrible cache behaviour.

It's enough to just take one random element and use it as a pivot.

Reply on news.ycombinator.com