Stable_sort profiling

Question

This page reports that whenever memory is insufficient, stable_sort comes down to an in-place algorithm with runtime O (n (log n) (log p)):

<sub> Sub difficulty >

If enough additional memory is available, linearithmic is at the distance between the first and the last: it performs element comparisons up to N * log ₂ (N) (where N is the distance) and many elements are moved to this. Otherwise, polylogologic at this distance: Performs up to N * log ₂ ² (N) comparisons of elements and up to this many element swaps.

I want to profile it against another algorithm in place with the same running time, so my question boils down to: how can I simulate a "lack of memory" so that a slow algorithm stable_sort in stable_sort ?

Answer 1

cplusplus.com is notoriously bad ... looking at the description of cppreference.com here

This function attempts to allocate a temporary buffer equal in size to the sequence to be sorted, usually by calling std :: get_temporary_buffer. If the distribution is not performed, a less efficient algorithm is selected.

get_temporary_buffer :

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

So, although technically this should be an underestimated behavior in order to specialize it for your own class in the std , you apparently do not do this for production code, and in practice it works very reliably and will allow you to intercept the memory request and refusal of return.

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