3 ms·
> 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 wo
by forrestthewoods 2y ago
> 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 2y agoThe 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 2y agoSlowness (lower throughput) is often the tradeoff for more predictable run time.
- forrestthewoods 2y agoDid you read the article? Median-of-median results in fewer comparisons than random.