[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.