Menu
Possible Duplicate:
which type of sorting is used in the function sort()?
Does std::sort implement Quicksort?
267
std::sort is most likely to use QuickSort, or at least a variation over QuickSort called IntroSort, which "degenerates" to HeapSort when the recursion goes too deep.
As the name suggests, qsort function uses QuickSort algorithm to sort the given array, although the C standard does not require it to implement quicksort. C++ sort function uses introsort which is a hybrid algorithm.
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.
The GNU Standard C++ library, for example, uses a 3-part hybrid sorting algorithm: introsort is performed first (introsort itself being a hybrid of quicksort and heap sort), to a maximum depth given by 2×log2 n, where n is the number of elements, followed by an insertion sort on the result.
There are two algorithms that are traditionally used.
std::sort is most likely to use QuickSort, or at least a variation over QuickSort called IntroSort, which "degenerates" to HeapSort when the recursion goes too deep.
From the standard:
Complexity: O(N log(N)) comparisons.
std::stable_sort is most likely to use MergeSort, because of the stability requirement. However note that MergeSort requires extra space in order to be efficient.
From the standard:
Complexity: It does at most N log2(N) comparisons; if enough extra memory is available, it is N log(N).
I have yet to see a std::sort implementing TimSort which is promising and has been adopted in Python (crafted for it in fact), Java and Android (to date).
88
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
