マージソート
マージソートは、1つの難しい問題をたくさんのやさしい問題に変えます。整列した2つのリストは、簡単に1つにまとめられるからです。どの部分も値1つになるまでリストを半分に分け、それらをマージして戻します。典型的な分割統治のアルゴリズムで、入力にかかわらず時間は n log n です。
考え方
マージは簡単な部分です。それぞれ整列した2つのリストがあれば、先頭の値を比べて小さい方を取ります。新しい先頭の値を比べて、また小さい方を取ります。一方のリストがなくなったら、もう一方の残りを後ろにつなげます。1ステップで値を1つ取るので、合計の長さが m の2つのリストのマージは、多くても m − 1 回の比較で済みます。マージソートはこれを使って並べ替えます。リストを半分に分け、それぞれをマージソートで並べ替え、2つの半分をマージします。
例
5, 1, 4, 2, 8 を考えます。これを 5, 1 と 4, 2, 8 に分けます。前半は 5 と 1 に分かれ、マージして 1, 5 になります。後半は 4 と 2, 8 に分かれます。2, 8 は 2 と 8 をマージしたもので、さらに 4 とマージして 2, 4, 8 になります。最後に 1, 5 と 2, 4, 8 をマージします。1、2、4、5 の順に取り、8 が残ります。比較は8回、書き戻しは12回、マージは4回です。
なぜ n log n なのか
分割のたびに部分は半分になるので、約 log₂ n 段で、どの部分も値1つになります。戻る途中では、各段のマージがすべての値を1回ずつ扱います。1段あたり書き戻しは n 回、比較は n 回未満です。合計で約 n log₂ n です。40個の値なら、書き戻しは216回、比較は最大177回です。同じリストでも、バブルソートでは780回の比較が必要になることがあります。入力の並びの影響もそれらのソートよりずっと小さく、40個の値の場合、整列済みのリストは100回、逆順は116回、ランダムなら約160回の比較です。
バッファと安定性
リスト内で隣り合う2つの半分をマージするには、一般的にはそれらをバッファにコピーし、順番に書き戻します。このアプリでは、そのバッファを2段目の棒として表示します。リストと同じだけの追加メモリが必要で、これがマージソートの主なコストです。その代わり安定なソートです。2つの先頭の値が等しいときは左半分の値が先になるので、等しい値は順序を保ちます。安定性は、レコードを複数の項目で順に並べ替えるときに重要です。
歴史と用途
John von Neumann は1945年にマージソートを記述しました。プログラム内蔵方式のコンピュータ向けに書かれた最初期のアルゴリズムの1つです。データを長い連続した単位で読み書きするため、テープ上のデータを並べ替える標準的な方法となり、今もメモリに収まらない大きなファイルに使われています。Python と、Java のオブジェクトの並べ替えで使われる Timsort は、すでに整列している部分を先に見つけ、短い部分には挿入ソートを使うマージソートです。
試してみよう
アプリを開いて「ステップ」を押してください。リストの網掛け部分が分割中またはマージ中の部分で、破線は中央を示します。マージが始まると、両方の半分がバッファの行に下ります。2つの先頭の値を比較し、小さい方が上に戻ります。カウンターに注目しましょう。書き戻しは同じ長さのリストならどれも同じで、比較は整列済みや逆順のリストで最も少なく、ランダムなリストで最も多くなりますが、約 n log₂ n を超えることはありません。
よくある質問
マージソートの時間計算量は?
最良、平均、最悪のいずれの場合も O(n log n) です。一般的な実装では、バッファ用に O(n) の追加メモリが必要です。
マージソートとクイックソートの違いは?
どちらもリストを分けて各部分を並べ替えます。マージソートは値を見ずに中央で分け、マージのときに仕事をします。クイックソートは分割のときに、ピボットを基準に値を動かして仕事をするので、マージは不要です。クイックソートはその場で並べ替え、実際には速いことが多いですが、不利な入力では n² まで遅くなることがあり、安定ではありません。マージソートは常に n log n で、安定です。
ボトムアップのマージソートとは?
再帰を使わない方式です。まず隣り合う値を1つずつマージして2個の組にし、次に2個の組を4個の組にし、というように、毎回長さを2倍にします。ここで示しているトップダウン方式と同じ量の処理をします。
マージソートは安定ですか?
はい。このアプリのように、値が等しいときに左半分の値を先に取れば安定です。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
マージソートを試す