c++ - 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)。