> In computer science, the median of medians is an approximate median selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, most commonly quickselect…
https://en.wikipedia.org/wiki/Median_of_medians
That's pretty much what I posted: median-of-ninthers is an evolution of median-of-medians, that I use to pick a better pivot whenever the pivot supplied by median-of-3 turns out to be bad.
Using it all the time would simply make quicksort/quickselect about twice as slow as it is now, but still faster than heapsort/heapselect. It's a better backstop algorithm than the common introsort/introselect.
There's also no randomisation, the implementation is completely deterministic, and depends exclusively on the input order.
And median-of-ninthers is faster, but median-of-medians is far from terrible, so calling it a galactic algorithm or completely useless in practice is far from the truth, IMO.
https://en.wikipedia.org/wiki/Median_of_medians
That's pretty much what I posted: median-of-ninthers is an evolution of median-of-medians, that I use to pick a better pivot whenever the pivot supplied by median-of-3 turns out to be bad.
Using it all the time would simply make quicksort/quickselect about twice as slow as it is now, but still faster than heapsort/heapselect. It's a better backstop algorithm than the common introsort/introselect.
There's also no randomisation, the implementation is completely deterministic, and depends exclusively on the input order.
And median-of-ninthers is faster, but median-of-medians is far from terrible, so calling it a galactic algorithm or completely useless in practice is far from the truth, IMO.