inplace_merge：是什么导致了 N*log(N) 与 N-1 的复杂性？

Question

从关于 inplace_merge 的 C++ 文档中，算法的复杂性是“如果使用内部缓冲区，则在比较中为线性 (N-1)，否则为 NlogN（其中 N 是范围 [first,last) 中的数字元素）”。内部缓冲区是什么意思，是什么导致 O(N-1) 与 O(NlogN) 的复杂性？

Answer 1

内部缓冲区只是由库分配的缓冲区，其大小足以在合并发生时保存合并的输出（合并完成后将其复制回原始范围）。如果使用这个额外的空间，合并可以在线性时间内完成。如果它不能或不使用单独的缓冲区来存储输出，则该操作将降级为具有运行时的通用排序O(n log n)。