Time and Space Complexity

時間計算量:

• 最良、平均、最悪の場合: O(n log n)
  • 配列は約 log n 回半分に分割され、各レベルでマージのために O(n) の処理が行われます。実行時間は入力の順序に依存しません。

空間計算量:

• O(n)
  • インプレース（その場）ソートとは異なり、マージソートはマージ中に新しい配列を構築するため、入力サイズに比例した追加のメモリが必要です。

まとめ:

• マージソートは高速で予測可能です：すべての場合において O(n log n) です。
• 安定ソートであるため、同じ値の要素の順序が保持されます。
• トレードオフは、マージに使用される追加の O(n) メモリです。