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

Question

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?

Swanhildas

Answer 1

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).

Demagogic

+1 for introducing me to the word "linearithmic" -- hadn't come across it before, but it's definitely a keeper :) – Barca

I don't know about C++03, but C++0x draft claims O(n log n) worst case complexity. And std::stable_sort is guaranteed to run in O(n log^2 n). – Selfacting

@ybungalobill: So it does. C++03 explicitly states that there is no worst-case complexity requirement. I wasn't aware that changes were made to the C++0x algorithm complexities in C++0x. (You're right about partial_sort; it only has quasilinear time complexity in both C++03 and C++0x). – Demagogic

Answer 2

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.

Aeroplane

So the worse complexity of std::sort() is also O(NlogN)? – Stringer

Answer 3

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

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

Barca

just read about introsort, pretty cool. reminded me of a sort with someone's first name in it, but i cant find it. nicksort, petesort, something like that. does anyone know what this is called? – Postaxial

@jon_darkstar: You may be thinking of Timsort. en.wikipedia.org/wiki/Timsort – Stairhead

Answer 4

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]

Scrapple

Answer 5

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.

Abadan

@James, sorry, copied the full snippet. last and first are the iterators passed to sort. – Abadan

Answer 6

The C++ standard specifies that the worst-case runtime of std::sort() is in O(n log n) - where n is number of sorted elements (cf. C++11, Section 25.4.1.1).

The standard doesn't specify a particular sorting algorithm.

Thus, a conforming std::sort() implementation is free to choose any algorithm that satisfies the above runtime requirement.

Note that C++ standard revisions before C++11 just required that the average runtime of std::sort() is in O(n log n).

See also the stackoverflow question What algorithms are used in C++11 std::sort in different STL implementations? to get an idea what actual sorting algorithms are used in real-world STL implementations.

Sulphanilamide

Answer 7

On average, linearithmic in the distance between first and last: Performs approximately N*log2(N) (where N is this distance) comparisons of elements, and up to that many element swaps (or moves).

Latium