Worst case performance and "impossibly unlikely" conditions
Posted Jan 13, 2012 20:16 UTC (Fri) by rgmoore
(✭ supporter ✭
In reply to: Worst case performance and "impossibly unlikely" conditions
Parent article: Denial of service via hash collisions
As I understand it, Perl switched to a random pivot at the same time they moved from quicksort to merge sort as their default algorithm. But that still has some potential problems. After all, if quicksort and merge sort are both O(NlogN), then which one is faster depends on implementation details, not algorithmic complexity. Adding extra processor cycles to pick the pivot may slow the whole thing down to the point that it loses its average case speed advantage over merge sort.
And it seems like using a random pivot would exacerbate the problem with quicksort not being a stable sort. Not only would items that compare the same not be guaranteed to stay in the same order after the sort, they wouldn't even be guaranteed to be in the same order if you sort the same list twice. I guess you already accepted that when you chose an unstable sort algorithm, but it still seems weird.
to post comments)