比較
書き戻し
マージ

  • マージ中の部分
  • 比較中
  • 書き戻し済み
  • マージ済み

マージソートの詳細

マージソート

マージソートは分割統治のアルゴリズムです。リストを半分に分け、それぞれを同じ方法で並べ替え、小さい方の先頭の値を取り出す操作を繰り返して、整列した2つの半分をマージします。半分がバッファの行に移り、順番に書き戻される様子を、好きな速度または1ステップずつ見て、比較、書き戻し、マージの回数を数えましょう。 「再生」で並べ替えを見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。タイルには比較回数、リストへの書き戻し回数、マージ回数が表示されます。棒の数や初期の並びを選ぶか、数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. 棒の数と初期の並びを選びます:ランダム、ほぼ整列済み、逆順、重複が多い。数値を自分で入力することもできます。
  2. 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると、並べ替えの好きな位置に移動できます。
  3. 各マージを見てみましょう。整列した2つの半分がバッファに下り、小さい方の先頭の値が1つずつ上に戻ります。

マージソートのしくみ

値が1つなら、すでに整列しています。それより長ければ、リストを2つの半分に分け、それぞれをマージソートで並べ替えます。次にマージします。各半分の先頭の値を見て、小さい方を結果に移し、両方の半分が空になるまで繰り返します。両方の半分が整列しているので、結果も整列しています。

常に n log n

半分に分ける操作を繰り返すと約 log₂ n 段になり、各段のマージですべての値が1回ずつ書き戻されるので、書き戻しは約 n log₂ n 回、比較は多くてもその回数です。バブルソート、選択ソート、挿入ソートと違い、n² で増えることはなく、リストの並びの影響もずっと小さくなります。代償はリストと同じ長さのバッファです。マージソートは安定でもあるため、Python や Java のソートの土台になっています。

よくある質問

マージソートはどう動きますか?

リストを半分に分け、それぞれをマージソートで並べ替え、2つの先頭の値のうち小さい方を取り出す操作を繰り返して、整列した半分をマージします。値が1つのリストはすでに整列しているので、分割はそこで止まります。

マージソートの比較回数は?

n個の値に対して、多くても約 n log₂ n − n + 1 回、少なくとも n log₂ n の約半分です。40個の値なら最大177回です。リストへの書き戻しは、n が同じなら常に同じ回数で、マージの各段で値1つにつき1回です。

マージソートはなぜ追加のメモリが必要ですか?

2つの半分をその場で速くマージするのは難しいため、一般的なマージソートは半分をバッファにコピーし、順番に書き戻します。バッファはリストと同じ長さで、これがクイックソートやヒープソートと比べたときの主な欠点です。

マージソートは安定ですか?

はい。2つの先頭の値が等しいときは左半分の値が先になるので、等しい値は元の順序を保ちます。

入力した数値はどこかに送信されますか?

いいえ。並べ替えはブラウザ内で動き、最後の設定はこのブラウザのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ