アルゴリズム・データ構造図鑑 · 入門

マージソート:整列済みの列を組み合わせる

分割と線形時間のマージから、最悪O(n log n)と安定性の条件を理解する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 小さく分けてから順に併合する
  2. [1,4,8]と[2,4,7]をマージする
  3. 各段の仕事を足し合わせる
  4. 安定性と外部整列への適性
  5. この記事をロゲイアに質問する理解を確かめる

小さく分けてから順に併合する

マージソートは列を二つへ分け、それぞれを整列させてから併合する分割統治法です。0または1要素の列は既に整列しています。整列済みの二列をマージするときは、両方の先頭候補を比べ、小さい方を出力してその列を一つ進めます。片側が空になれば、残る列を続けて出力できます。分割するだけで並ぶのではなく、各段で整列条件を回復するマージが仕事の中心です。

[1,4,8]と[2,4,7]をマージする

最初に1と2を比べて1を、次に4と2を比べて2を出力します。続く4同士は同じ値なので、元の順序を保ちたいなら左の列の4を先に選びます。その後に右の4、7、8が続き、結果は[1,2,4,4,7,8]です。各要素は一度ずつ出力されるため、長さaとbの列のマージはO(a+b)です。比較するキーの計算自体が高価なら、その費用も別に数えます。

各段の仕事を足し合わせる

配列をおおむね半分ずつに分けると、分割の深さはO(log n)です。同じ深さにあるマージ処理の要素数を合計するとO(n)なので、全体で最悪O(n log n)になります。標準的な配列向け実装では、マージ先の補助配列としてO(n)の追加領域を使います。再帰呼び出しのスタックも必要です。「どの実装でも追加領域O(1)」とはいえず、配列か連結リストかでも実装上の選択が変わります。

安定性と外部整列への適性

同じキーの要素の元の順序を保つ性質を安定性と呼びます。マージソートでは、等しいキーで左側を先に出力するなどの規則によって安定性を保てます。すでに日付順になったデータを担当者名で安定整列すれば、同じ担当者の中で日付順が残ります。また、順次読み書きでマージできるため、メモリに収まらないデータを複数の整列済みファイルへ分けて処理する外部整列にもつながります。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ