2 ms·
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 sele
by gpderetta 4y ago
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.
- 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.