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?
1 Answers
The "space complexity" of std::sort is not defined. However, it is not allowed to dynamically allocate memory (as it is not allowed to throw std::bad_alloc unless your types do when copied/moved). 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.
Related