std::stable_sort: How to choose memory-optimised algorithm over time-optimised algorithm?

Question

I wish to make use of std::stable_sort. The complexity of the algorithm is stated as

O(N·log^2(N)), where N = std::distance(first, last) applications of cmp. If additional memory is available, then the complexity is O(N·log(N)). http://en.cppreference.com/w/cpp/algorithm/stable_sort

In my application, memory is critical, therefore, I would prefer std::stable_sort to use the memory-optimised O(N·log^2(N)) algorithm, rather than the time-optimised O(N·log(N)) algorithm. I understand that the time-optimised version will only be chosen if it is safe to do so (memory available). However, I aim to benchmark my application, and therefore, as memory is critical, want to benchmark the algorithm when memory consumption is lowest. As my system currently has enough memory to allocate the buffer, it will automatically chose the O(N·log^2(N)) version of std::stable_sort. I would therefore like to assert to std::stable_sort to take the memory-optimised version. Is this possible?

The execution policy appears to be a parameter that can modify the algorithm, however, it appears to only alter the extent of parallelism. http://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t

Although choosing either the parallel or sequential version may actually be choosing the O(N·log(N)) or O(N·log^2(N)) versions respectively, this is not stated anywhere on the webpage.

I wonder if anyone has any experience in asserting this choice. If so would they be able to provide any advice?

Answer 1

You can look into your headers and see which function gets called if the extra buffer isn't available. For me on gcc it is

    std::__inplace_stable_sort(__first, __last, __comp);

This is of course not standards compliant. The __inplace_stable_sort is a helper function and is not intended to be used directly.

The call by std::stable_sort to this function is a result of the following code

typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
  _TmpBuf __buf(__first, __last);

  if (__buf.begin() == 0)
std::__inplace_stable_sort(__first, __last, __comp);
  else
std::__stable_sort_adaptive(__first, __last, __buf.begin(),
                _DistanceType(__buf.size()), __comp);