Does std::sort implement Quicksort?

Question

Possible Duplicate:
which type of sorting is used in the function sort()?

Does std::sort implement Quicksort?

Solution

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 log²(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).

Comments

[ereOn]

While in this case it is probably true, I would be very careful about what I read on Wikipedia. When it comes to have a reference, cite the standard instead.

[Matthieu M.]

std::sort does not work on linked-lists, so it's a non-issue.

[Antony Stubbs]

@maxim-yegorushkin: the Wikipedia article also appears to claim introsort switching to insertion sort instead of heapsort :/ en.wikipedia.org/wiki/Sort_(C%2B%2B) "The GNU Standard C++ library, for example, uses a hybrid sorting algorithm: introsort is performed first, to a maximum depth given by 2×log2 n, where n is the number of elements, followed by an insertion sort on the result."

[NathanOliver]

Because QuickSort has a worst case of O(N^2), would you mind updating the answer since that can no longer be used in a C++11+ complaint implementation?