c++ - What algorithms are used in C++11 std::sort in different STL implementations?

Question

The C++11 standard guarantees that std::sort has O(n logn) complexity in the worst case. This is different from the average-case guarantee in C++98/03, where std::sort could be implemented with Quicksort (maybe combined with insertion sort for small n), which has O(n^2) in the worst case (for some specific input, such as sorted input).

Were there any changes in std::sort implementations in different STL libraries? How is C++11's std::sort implemented in different STLs?

Answer 1

The question is, how can STL say std::sort worst case is O(N log(N)), even though it is in essence a QuickSort. STL's sort is IntroSort. IntroSort is in essence a QuickSort, the difference introduced change the worst case complexity.

---

QuickSort worst case is O(N^2)

What ever partitioning you choose, there exist a sequence that QuickSort will run on O(N^2). The partitioning you choose only decreases the probability of the worst case to occur. (Random Pivot Selection , Median-Of-Three, etc.)

EDIT: Thanks to @maxim1000 s correction. Quicksort with pivot selection algorithm Median of Medians has O(N log(N)) worst case complexity, but due to the overhead it introduces it isn't used in practice. It shows how good selection algorithm, can change the worst-case complexity through pivot selection, theoretically.

---

What does IntroSort do?

IntroSort limits the branching of QuickSort. This is the most important point, that limit is 2 * (log N). When limit is reached, IntroSort can use any sorting algorithm that has worst case complexity of O(N log(N)).

Branching stops when we have O(log N) subproblems. We can solve every subproblem O(n log n). (Lower case n stands for the subproblem sizes).

Sum of (n log n) is our worst case complexity, now.

For the worst case of QuickSort; assume we have an already sorted array, and we select always the first element in this array as the pivot. In every iteration we get rid of only the first element. If we went this way until the end, it would be O(N^2) obviously. With IntroSort we stop QuickSort, when we reach a depth log(N), then we use HeapSort for the remaining unsorted array.

16 -> 1  /**N**/
   
    > 15 -> 1 /**N - 1**/
         
          > 14 -> 1 /**N - 2**/
               
                > 13 -> 1 /**N - log(N)**/  
                     
                      > 12 /**(HeapSort Now) (N - log(N)) log (N - log(N))**/

Sum them up;

Until branching stops, N + (N - 1) + ... + (N - log(N)) operations done. Instead of using gauss to sum up, we can simply say N + (N - 1) + ... + (N - log(N)) < N log(N).

The HeapSort Part is (N - log(N)) log(N - log(N)) < N log(N)

Overall complexity < 2 N log(N).

Since the constants can be omitted, the worst case complexity of IntroSort is O(N log(N)).

---

Added Info: GCC STL implementation source code is here. Sort function is at line 5461.

Correction: *Microsoft .NET* sort Implementation is IntroSort since 2012. Related information is here.