std::sort now guarantees complexity O(N * log N) under C++11 Standard

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.

Leave a comment

Filed under C++, Programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s