c++ - inplace_merge に追加のメモリが必要な理由は何ですか

Question

Q: inplace_merge: N*log(N) と N-1 の複雑さの原因は何ですか?

しかし、私が本当にAに興味を持っている部分が明確に説明されていないので、私は答えが不十分だと思います. より具体的には、明確ではありません(私には:)) inplace_merge が線形時間でメモリを追加せずにインプレース マージを行うことができないのはなぜですか?一定時間のスワップ。

Answer 1

ソートされた 2 つのサブシーケンスをマージするとします。

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
               ^   ^

サブシーケンスの 1 つの終わりに達したので、停止します。マージされたシーケンスはソートされていますか?