Menu
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?
305
The std::sort is a sorting function that uses the Introsort algorithm and have the complexity of O(N log(N)) where N= std::distance(first, last) since C++11 and the order of equal elements is not guaranteed to be preserved[3]. The gcc-libstdc++ also uses Introsort algorithm.
Most implementations of std::sort use quicksort, (or usually a hybrid algorithm like introsort, which combines quicksort, heapsort and insertion sort).
std::sort() is a built-in function in C++'s Standard Template Library. The function takes in a beginning iterator, an ending iterator, and (by default) sorts the iterable in ascending order. The function can also be used for custom sorting by passing in a comparator function that returns a boolean.
first – is the index (pointer) of the first element in the range to be sorted. last – is the index (pointer) of the last element in the range to be sorted. For example, we want to sort elements of an array 'arr' from 1 to 10 position, we will use sort(arr, arr+10) and it will sort 10 elements in Ascending order.
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.
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.
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.
176
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
