STL Sort vs median of medians

开发者_如何学Python

std::sort() uses the Introsort algorithm that switches between quick & heap sort depending upon the current partitioning ratio.

Is there a practical disadvantage to implementing Median-of-Medians Quicksort in place of Introsort? After all, it's harder to model a mixture of sorting algorithms theoretically & compute their worst case complexity - though I assume Introsort's would be O(N log N).

---

See Musser's original paper on Introsort. Basically, though Median of Medians and Introsort are the same asymptotically, Introsort does less constant work per item and is generally faster. The paper does mention that Median of Medians would be fine as a fallback sort instead of Heap Sort.

David R. Musser. Introspective Sorting and Selection Algorithms. [Postscript version]

---

From what I remember, Quicksort performs badly on collections that are sorted or very nearly sorted - O(n^2). Check out Wikipedia's page on Introsort - with a compelling statistic on Introsort vs. Quicksort.