Profiling stable_sort

Question

This page tells that whenever there is not enough memory, stable_sort reduces to an in-place algorithm with running time O(n(log n)(log n)):

_Complexity

If enough extra memory is available, linearithmic in the distance between first and last: Performs up to N*log₂(N) element comparisons (where N is this distance), and up to that many element moves. Otherwise, polyloglinear in that distance: Performs up to N*log₂²(N) element comparisons, and up to that many element swaps.

I want to profile it against another in-place algorithm with the same running time, so my question reduces to: how can I simulate a "lack of memory" so that the slower algorithm is performed in stable_sort?

Answer 1

cplusplus.com is notoriously bad... looking at cppreference.com's description here

This function attempts to allocate a temporary buffer equal in size to the sequence to be sorted, typically by calling std::get_temporary_buffer. If the allocation fails, the less efficient algorithm is chosen.

get_temporary_buffer is:

template< class T >
std::pair< T*, std::ptrdiff_t > get_temporary_buffer( std::ptrdiff_t count )

So, while it will technically be underfined behaviour to specialise it for your own class in the std namespace, you're presumably not doing this for production code and in practice it's extremely likely to work reliably and would let you intercept the memory request and return failure.

namespace std
{
    template <>
    std::pair<My_Class*, std::ptrdiff_t>
    get_temporary_buffer(std::ptrdiff_t)
    { return {0, 0}; }
}