Re:Why don't they just..?
by tedunangst on Monday August 20, 2012 @09:04AM
(#4407326)
Sometimes you don't know what the edge cases are because you don't know what the everything else is. If you return something sorted, somebody will write a consumer that depends on the sorting. If you change backends and return things in a different order, you've broken their code. Sure, their code was broken from the start, but it used to work, now it doesn't, and you're the guy who changed something. The only way to prevent this, randomly sorting every unsorted collection you export, isn't feasible to reliably maintain.
[ Parent
| on HN ]
> The only way to prevent this, randomly sorting every unsorted collection you export, isn't feasible to reliably maintain.
It's feasible to maintain. But people might rely on it, too. As a random example (and easily avoidable example), quicksort works with random input, but 'breaks' for pre-sorted input.
That depends on the pivot chosen. If your quicksort implementation actually hits n^2 behavior with sorted input, it's probably not the best implementation.
Any implementation can hit n^2 with random input. It's just highly unlikely.