Motivation

マージソートは、問題をより小さな部分問題に分割し、それぞれを解決してから、その結果を組み合わせます。すでにソートされた2つのリストをマージするその結合ステップが、このアルゴリズムの核心です。

なぜマージソートを学ぶのか？

• 高速で予測可能： 最良、平均、最悪のケースで O(n log n) の時間で実行されます。
• 安定： 同等の要素は元の相対的な順序を維持します。
• 大規模なデータに最適： データがメモリに収まらない場合（外部ソート）や、連結リストに対してうまく機能します。
• 分割統治法： 多くの高度なアルゴリズムで使用されるパターンを学ぶことができます。