STL Sort vs median of medians

Question

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).

Answer 1

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.