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

Question

As in the title - what is the memory complexity of std::sort() and std::sort_heap() ? (The latter requires std::make_heap() , so I would like to know its memory complexity.)

I tried searching on these sites: http://www.cplusplus.com/reference/ http://en.cppreference.com/w/ , but I missed this or only mentioned the complexity of the time. Is the memory complexity of these functions anywhere (in the C ++ standard or another document)? Or maybe it depends on the implementation?

Answer 1

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

Quality of implementation. Different implementations use memory more efficiently than other implementations. In addition, the standard allows specialization for std::sort for different categories of iterators, allowing the implementation to choose between several different parameters, as long as the complexity (time) meets the requirements. Data complexity is not time, but the number of comparisons. The implementation could perform swapping operations N³.

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

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

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