4 ms·
A better way to improve the worst case to O(n log n) time is to use the "Introsort" optimization.[1] Keep track of the recursion depth (with optimized-out tail-
by ggchappell 13y ago
A better way to improve the worst case to O(n log n) time is to use the "Introsort" optimization.[1] Keep track of the recursion depth (with optimized-out tail-recursive calls counted). If the depth exceeds k * log_2(n) [maybe k = 2?], then switch to Heap Sort for the current sublist.
This optimization is useful in practice. The result is a sort that is as fast as Quicksort on average, but unlike Quicksort runs in O(n log n) time. So, for example, the C++ Standard Library function std::sort will use Introsort in any good implementation.
Despite its wonderfulness, Introsort is strangely little known. Algorithms texts rarely mention it, for some reason.
[1] https://en.wikipedia.org/wiki/Introsort https://en.wikipedia.org/wiki/Introsort
- eru 13y agoIntrosort is good in practice, but it's not a quicksort. If you are interested in theory, the pivot in linear time algorithm (like QuickSelect) is truly marvelous. It also provides a good study of how simple a randomized algorithm can be, and how to de-randomize it into something much more complicated but deterministic. But in some sense that complications help you understand, because otherwise, randomize algorithms are often `magic'.
- ggchappell 13y agoI'm familiar with the median-of-medians linear-time selection algorithm (a.k.a. BFPRT). But I don't recall ever seeing a construction of a pivot-finding algorithm using de-randomization. Do you have a reference for this?
- eru 13y agoSorry, that was from memory. (Can't you interpret the BFPRT as a de-randomization?) Anyway, slightly modified my point still stands: BFPRT is way more complicated (and harder to come up with) than randomized QuickSelect.