What is the time complexity of std::sort() in the C++ standard library?

What is the complexity of std::sort() in the C++ Standard Library? Which sort is applied? Is there any rule of applying any particular sorting algorithm there?

Before C++11:

std::sort must have average case linearithmic (n log n) time complexity. Any algorithm may be used so long as that time complexity requirement is met. There is no worst case time complexity requirement.

If you want a guaranteed worst case time complexity function, use std::stable_sort, which has quasilinear worst case time complexity (n log^2 n).

The standard guarantees

From the C++11/14 standard, std::sort is guaranteed to have:

§25.4.1.1/3

Complexity: O(N log(N)) (where N == last - first) comparisons.

The other, stable, standard sorting algorithm (namely std::stable_sort) is guaranteed to have:

25.4.1.2/3

Complexity: It does at most N log²(N) (where N == last - first) comparisons; if enough extra memory is available, it is N log(N).

For std::forward_list::stable, instead:

23.3.4.6/26

Complexity: Approximately N log(N) comparisons, where N is distance(begin(), end()).

The same goes for std::list:

23.3.5.5/31

Complexity: Approximately N log(N) comparisons, where N == size().

Sorting algorithm

The C++ standard does not specify which sorting algorithm to apply in any of the above cases. This would be oftentimes and unnecessary implementation restriction.

If you need to know you might have luck looking in a specific compiler specification. For example for GNU GCC you would start here.

The complexity is O(n log n). Some common implementations use introsort as far as I know:

http://en.wikipedia.org/wiki/Introsort

http://en.wikipedia.org/wiki/Sort_(C%2B%2B)

The specific sorting algorithm is not mandated and may vary across implementations. 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.[1] Whatever the implementation, the complexity should be O(n log n) comparisons on the average. [2]

If you mean std::sort():

This is from C++03 standard, section 25.3. The performance guarantee:

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last,
    Compare comp);

1 Effects: Sorts the elements in the range [first, last).

2 Complexity: Approximately N log N (where N == last - first) comparisons on the average.