inplace_merge: What causes a complexity of N*log(N) vs. N-1?

Question

From C++ documentation on inplace_merge, the complexity of the algorithm is "Linear in comparisons (N-1) if an internal buffer was used, NlogN otherwise (where N is the number elements in the range [first,last))". What do they mean by an internal buffer and what causes a complexity of O(N-1) vs. O(NlogN)?

Answer 1

To expand on the other answer(s):

• At least in libstdc++ and libc++, the "internal buffer" is provided by calling std::get_temporary_buffer, an obscure yet standard routine in the STL. This routine has been deprecated in C++17, basically because it's confusing and kind of dumb. See this question for details, or read Stephan T. Lavavej's original deprecation proposal.

• In libstdc++, get_temporary_buffer is implemented as a call to operator new. (Source)

• In libc++, the get_temporary_buffer is implemented as a call to operator new. (Source)

• I don't know whether inplace_merge uses get_temporary_buffer in MSVC's standard library, but I would bet money that it does.

• In MSVC, it has been reported that get_temporary_buffer is implemented as a call to operator new.

You can write a program to observe this call to operator new firsthand by overriding operator new in the global namespace:

#include <algorithm>
#include <cstdio>
#include <cstdlib>

void *operator new(size_t nbytes, const std::nothrow_t&) noexcept
{
    puts("hello from operator new!");
    return malloc(nbytes);
}

int main()
{
    int a[32] = {
        1,1,1,2,3,4,4,5,5,5,5,6,6,8,9,9,
        1,1,2,3,3,3,4,4,5,5,7,8,9,9,9,9,
    };
    std::inplace_merge(&a[0], &a[16], &a[32]);  // "hello from operator new!"
    (void)a;
}

TL;DR: The "internal buffer" is allocated on the heap by calling operator new. Implementations are not required to call operator new, but in practice they all do. Stay far, far away from inplace_merge if you value your heap.