What's the memory complexity of std::sort() and std::sort_heap()?

Question

As in the title - what's the memory complexity of std::sort() and std::sort_heap()? (The latter requires std::make_heap() so I'd like to know its memory complexity as well.)

I've tried searching on these sites: http://www.cplusplus.com/reference/ http://en.cppreference.com/w/ but either I missed it or they only mention the time complexity. Is the memory complexity of said functions specified anywhere (in C++ standard or some other document)? Or maybe that is implementation-dependent?

Answer 1

For std::sort() I found an answer on Cboard, which pretty much says:

Quality of implementation issue. Different implementations use memory more effectively than other implementations. Beyond that, the standard allows specializations for std::sort for different iterators categories allowing the implementation to choose between a few different options so long as the complexity (time) matches the requirements. The complexity given is not even time, but numbers of comparisons. The implementation could perform N³ swap operations.

The memory overhead for most implementations of std::sort would be related to the depth of recursion and the number of local variables stored onto the stack for each level of recursion. The HP / Microsoft STL implementation of std::sort uses Quicksort until/unless it detects that the recursion level is getting too deep in which case it switches to heap sort. If the size is small, such as 32 or less, then it uses Insertionsort.

You can see a comparison of the algorithms, in the Wikipedia page and estimate the memory complexity.

Similarly, I suspect that the other two algorithms fall into the same case.