3 ms·
I don't think you can recommend Quicksort unless you know something about the distribution of the elements to be sorted, or am I mistaken. After all, Quicksort
by Tichy 19y ago
I don't think you can recommend Quicksort unless you know something about the distribution of the elements to be sorted, or am I mistaken. After all, Quicksort can be very slow under certain conditions.
- aston 19y agoQuicksort's worst case involves bad pivot picking. The randomized version pretty much makes that a non-issue unless you're incredibly unlucky. Even still, with median-of-medians you can guarantee a deterministic worst case of nlog(n), so that's not true.
- jey 19y agoYou can keep track of the performance of Quicksort then fallback to Insertion Sort if Quicksort is sucking. This is how std::sort() works in most C++ implementations.