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

c++ stl time-complexity
Hari Chaudhary picture Hari Chaudhary · Dec 19, 2010 · Viewed 54.6k times · Source

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?

Answer

James McNellis picture James McNellis · Dec 19, 2010

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

Related questions

C++ std::unordered_map complexity

I've read a lot about unordered_map (c++11) time-complexity here at stackoverflow, but I haven't found the answer for my question. Let's assume indexing by integer (just for example): Insert/at functions work constantly (in average time), so this example …

Read More
What is the easiest way to initialize a std::vector with hardcoded elements?

I can create an array and initialize it like this: int a[] = {10, 20, 30}; How do I create a std::vector and initialize it similarly elegant? The best way I know is: std::vector<int> ints; ints.push_back(10); ints.…

Read More
How do I erase an element from std::vector<> by index?

I have a std::vector<int>, and I want to delete the n'th element. How do I do that? std::vector<int> vec; vec.push_back(6); vec.push_back(-17); vec.push_back(12); vec.erase(???);

Read More