[kccqzy]

> Quickselect gets us linear performance, but only in the average case. What if we aren’t happy to be average, but instead want to guarantee that our algorithm is linear time, no matter what?

I don't agree with the need for this guarantee. Note that the article already says the selection of the pivot is by random. You can simply choose a very good random function to avoid an attacker crafting an input that needs quadratic time. You'll never be unlucky enough for this to be a problem. This is basically the same kind of mindset that leads people into thinking, what if I use SHA256 to hash these two different strings to get the same hash?

[mitthrowaway2]

It's a very important guarantee for use in real-time signal processing applications.

[forrestthewoods]

> I don't agree with the need for this guarantee.

You don’t get to agree with it or not. It depends on the project! Clearly there exist some projects in the world where it’s important.

But honestly it doesn’t matter. Because as the article shows with random data that median-of-medians is strictly better than random pivot. So even if you don’t need the requirement there is zero loss to achieve it.

[kccqzy]

The median-of-median comes at a cost for execution time. Chances are, sorting each five-element chunk is a lot slower than even running a sophisticated random number generator.

[Quekid5]

Slowness (lower throughput) is often the tradeoff for more predictable run time.

[forrestthewoods]

Did you read the article? Median-of-median results in fewer comparisons than random.