arrays - 配列の並べ替え（時間計算量）

Question

ソートされたセル0〜Nと、ソートされていないM+NまでのセルN+1を持つ配列がある場合。配列をソートするのに最適な時間計算量はどれくらいですか？

ありがとう！

---

編集：

ありがとう ！！その場でそれをやりたいのなら、それは複雑さを変えるでしょう？

Answer 1

まず、並べ替えられていない M 個の要素だけを並べ替えます。これには、比較ベースの並べ替え (クイック並べ替え、マージ並べ替え、ヒープ並べ替えなど) を使用すると、O(M log M) の時間がかかります。

次に、ソートされた 2 つのセグメント (長さ N と M) をマージします。これには O(M + N) の時間がかかります。

したがって、比較ベースのソートを使用した最適な時間計算量は O(M + N + M log M) です。