CODEWITHSUNDEEP
c++sortingstd
Srivatsan Talkad
Srivatsan Talkad

Reputation: 81

What is the space complexity of std::sort in the C++ Standard Template Library?

I always thought it the space complexity is O(1) but I looked online and it uses different sorting algorithms at different stages which has confused me, what exactly is the space complexity of std::sort and when are they different?

Upvotes: 8

Views: 4733

Answers (1)

Nicol Bolas
Nicol Bolas

Reputation: 473447

The "space complexity" of std::sort is not defined. However, it is not allowed to dynamically allocate memory (only the ExecutionPolicy overloads are allowed to throw std::bad_alloc). So the only space it could take up is stack space. And its allowed to take up however much an implementation desires.

sort tends to be implemented as some variation of quick-sort, so that tends to be recursively implemented, so it would probably use O(log(n)) calls on average.

Upvotes: 7

Related Questions