On 24/03/2016 17:37, Gonzalo BG wrote:
As a base line would also be possible to show the performance of `std::inplace_merge` and `std::stable_sort` when `std::get_temporary_buffer` returns a zero sized buffer? That is, in the case that no memory can be allocated, how much better are these new sorting algorithms compared to the std ones?
We would need to implement the algorithm ourselves as there is no way to stub get_temporary_buffer() to return zero unless we modify STL headers, which does not seem very clean ;-) The worst case complexity of STL fallback algorithms is worse, which means that with big ranges the new algorithm will always win. However, the algorithm could have a much bigger constant factor that makes it inefficient for smaller ranges. I'll try to see how STL implementations implement the fallback inplace_merge and maybe implement it and add it to the benchmarks. Best, Ion