3 ms·
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
by ErikCorry 4y ago
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.
- gpderetta 4y agoTo 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.
- ErikCorry 4y agoThat'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.
- Laakeri 4y agoIt's enough to just take one random element and use it as a pivot.