c++ - inplace_merge 需要额外内存的原因是什么

Question

我知道这个问题： inplace_merge：是什么导致 N*log(N) 与 N-1 的复杂性？

但我发现答案不令人满意，因为我对 A 真正感兴趣的部分没有得到清楚的解释。更具体地说，不清楚（对我来说:)）为什么不能 inplace_merge 在线性时间内进行就地合并而无需任何额外的内存，只需从开始和当前项目大于第二范围（中间，结束）就可以恒定时间交换。

Answer 1

想象一下，您正在合并两个已排序的子序列：

11, 12, 13, 14     1,  2,  3,  4
^                  ^

1 < 11，所以你交换：

 1, 12, 13, 14    11,  2,  3,  4
     ^             ^

11 < 12，交换：

 1, 11, 13, 14    12,  2,  3,  4
         ^         ^

12 < 13，交换：

 1, 11, 12, 14    13,  2,  3,  4
             ^     ^

13 < 14，交换：

 1, 11, 12, 13    14,  2,  3,  4
               ^   ^

您已到达其中一个子序列的末尾，因此您停止了。合并后的序列是否排序？