マージソートとは？
マージソート(Merge Sort)は、配列を半分に分け続け、これ以上分けられないところまで降りたあと、整列済みの2つの断片を統合(merge)しながら昇ってくる分割統治アルゴリズムです。「分ける」のは簡単で、本当の仕事は「統合する」ところで起こります。
核心の一行: 「既に整列された2つの配列を統合するのは速い」。 2つの断片がそれぞれ整列されていれば、前から小さい方を1つずつ取るだけでO(n)で統合できます。
核心は統合(merge)
整列済みの2配列 A, B を統合するとします。
1. AとBの先頭を指すポインタを置く。
2. 2つのポインタが指す値のうち小さい方を結果に入れ、そのポインタだけ1つ進める。
3. 片方が空になったら、残りをそのまま連結する。
各要素をちょうど1回だけ見るので統合はO(n)です。この統合を深さlog n回繰り返すので全体がO(n log n)です。
動作原理
ステップ1. 区間 [lo, hi] の中央 mid を基準に、左 [lo, mid] と右 [mid+1, hi] に分けます。
ステップ2. 左と右をそれぞれ再帰で整列します。区間サイズが1なら既に整列済みとして止めます(基底ケース)。
ステップ3. 整列済みの2区間を上の統合手順で1つの整列区間に合わせます。
ステップ4. 再帰が昇るにつれ大きな区間が統合され、最後に全体が整列します。
「分ける」動作と「統合する」動作は別物です。AlgoNoteの可視化も分割ステップと統合ステップを分けて示します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(n log n) |
| 空間 | O(n) |
分割の深さが常にlog nで各深さの統合がO(n)なので、入力が何であれ常にO(n log n)を保証します(クイックソートと違い最悪ケースがない)。代わりに統合用の一時配列が必要で空間はO(n)です。
例で追ってみる
[5, 2, 8, 1] を整列します。
- •分割:
[5, 2]と[8, 1] - •それぞれ整列:
[2, 5]と[1, 8] - •統合: 2 vs 1 → 1、2 vs 8 → 2、5 vs 8 → 5、残り8 →
[1, 2, 5, 8]
小さな断片が整列されたまま統合され、全体が完成します。
よくあるミス
- •一時配列: 統合結果を一時配列に入れてから元配列にコピーする手順を忘れると値が上書きされます。
- •安定性の維持: 値が等しいとき左(前の区間)の値を先に入れると安定ソートになります(同値の元の順序を保存)。
- •midの計算:
(lo + hi) / 2は大きな数でオーバーフローの危険 →lo + (hi - lo) / 2が安全です。
AlgoNoteで直接確認しましょう
配列がどう半分に割れ、整列済みの2断片が小さい順に統合されるかをAlgoNoteでステップごとに確認できます。