I learnt recently that in the C++11 Standard, std::sort is required to have complexity O(N * log N) – not “on average N * log N with a worst case O(n^2)”, but guaranteed O(N * log N). This follows David Musser’s paper on Introspective Sorting and Selection.
Musser’s IntroSort uses QuickSort, but also monitors the number of partitions that have occurred. For example, one might use “median-of-3” to pick each pivot, but that could cause the O(N^2) behaviour if pathological sequence is encountered. In the paper, such a sequence is described by construction. IntroSort switches to HeapSort (which guarantees O(N * log N) performance) once the number of QuickSort partitions reaches 2 * log N. Musser proves that the overall algorithm performance remains O(N * log N).
As pointed out on StackOverflow, std::nth_element could be re-implemented with similar benefits:
Ideally exactly the same should apply std::nth_element but the ISO C++ 2011 standard has not tightened up the complexity requirements. So std::nth_element could be O(N * N) in the worst case.
musingstudio 