マージソートの実行時間::すべての要素が同じです

Question

すべての要素が同じサイズnの配列があるとします。何がO（n）になりますか？線形であろうか？

Answer 1

これは、アルゴリズムの実装方法によって異なります。

mergesortの標準的な "バニラ"実装では、配列をソートするのに必要な時間は、各ステップで必要とされるマージが線形時間を取るため、常にΘ（n log n）になります。

ただし、適切な最適化を行うと、これを時間O（n）で実行することができます。多くのマージソートの実装では、入力配列は連続的に変更され、より大きな範囲と大きい範囲がソートされ、マージ・ステップが発生すると、アルゴリズムは外部バッファを使用して2つの隣接ソート範囲をマージします。その場合、マージを行う前に、最初の範囲の最後の要素が2番目の範囲の最初の要素以下であるかどうかを確認してください。そうであれば、2つの範囲は既にソートされているので、マージは必要ありません。

この最適化を実行し、すべての要素がすでにソートされている配列をソートするとします。何が起こるのですか？さて、mergesortを呼び出すたびに、さらに2つの呼び出しが呼び出されます。返された後、ソートされた範囲の終点をチェックすることができ、すでにソート順になっていることに気づくでしょう。全体として、これはコールあたりO（1）作業を行うので、我々は、アルゴリズムの時間複雑さのために、この漸化式を有する：

T（N）= 2T（N/2）+ O（1）

を

これはO（n）に解決されるため、直線的な作業のみが行われます。