合併ソート（マージソート）完全ガイド：仕組み・計算量・実装と実務で使える最適化テクニック
エバープレイ編集部合併ソートとは
合併ソート（マージソート、Merge Sort）は、比較ベースの安定な整列アルゴリズムの一つで、分割統治法（divide and conquer）を用いて配列やリストを整列します。配列を半分に分割してそれぞれを整列し、最後に二つの整列済み部分列を「合併（マージ）」して一つの整列済み列を作るという手順を再帰的に繰り返します。時間計算量は平均・最悪・最良いずれも O(n log n) であり、安定性を保てる点や外部ソート（ディスク等を使う大規模データのソート）への応用が得意な点が特徴です。
アルゴリズムの原理（分割→整列→合併）
合併ソートは以下の3段階で動作します。
- 分割（Divide）: 配列をほぼ二等分する。
- 整列（Conquer）: 各半分を再帰的に合併ソートで整列する。
- 合併（Combine）: 二つの整列済み部分列を一回の線形時間でマージして一つにする。
「合併」操作は典型的には二つのポインタを用いて先頭から小さい方を取り出し、外部バッファに順に書き出す手続きであり、この合併に要する時間は要素数の和、すなわちO(n)です。
簡単な擬似コード（トップダウン再帰版）
function merge_sort(A):
if length(A) ≤ 1:
return A
mid = floor(length(A) / 2)
left = merge_sort(A[0:mid])
right = merge_sort(A[mid:end])
return merge(left, right)
function merge(L, R):
result = empty list
i = 0; j = 0
while i < length(L) and j < length(R):
if L[i] ≤ R[j]:
append L[i] to result; i += 1
else:
append R[j] to result; j += 1
append remaining elements of L or R to result
return result
計算量の解析
合併ソートの時間計算量は、配列を半分に分割して再帰的にソートし、マージに O(n) 時間を要するため、次の漸化式で表されます。
T(n) = 2T(n/2) + O(n)
これはマスター定理により T(n) = O(n log n) と解けます。最良・平均・最悪いずれのケースでも O(n log n) になります。空間計算量に関しては、典型的な実装（配列を使う場合）で追加の配列を確保するため O(n) の追加メモリが必要です。リンクリストに対する実装では追加メモリを O(1) に抑えられる場合もあります。
安定性について
合併ソートは適切に実装すれば安定（stable）なソートアルゴリズムになります。安定性とは、キーが等しい要素の相対順序がソート後も保持される性質です。合併操作で「≤」の比較を左側優先にすることで、同値の要素は元の順序どおりに並べられます。
実装のバリエーション
- トップダウン再帰（上記）: 理解しやすく最も一般的。
- ボトムアップ反復（バトムアップ）: 部分配列のサイズを 1, 2, 4, 8... と倍増させながら隣接するブロックをマージしていく。再帰を使わずにループで実装可能で、再帰オーバーヘッドを避けられる。
- インプレース変種: 追加領域をほとんど使わずにマージする試みもあるが、実装が複雑になり定数因子や計算量が増えることが多い。一般に配列のインプレースマージは難易度が高い。
- リンクリスト向けマージソート: リンクリストは分割とマージがポインタ操作で済むため、追加配列なしで安定かつ効率的に実装できる（追加メモリ O(1)）。
- 外部マージソート（外部ソート）: データがメモリに乗り切らない場合、ディスク上に複数の「ラン」を作り、それらを k-way マージすることで大規模データをソートする。これはデータベースや分散処理で重要。
- 並列マージソート: 分割されたブロックを別スレッド/プロセスで並列にソートし、マージも並列化できる。並列化効率はハードウェアや実装に依存する。
実用上の最適化技法
- 小さい部分配列は挿入ソートに切り替える（例: 要素数 <= 32 など）。小規模では挿入ソートの方が高速なことが多い。
- 一時バッファを使い回す：再帰ごとに新しい配列を確保するとコストが高いので、外側で一時配列1つを確保し再利用する実装が多い。
- 既に整列済みの隣接ブロックはマージをスキップする（適応的整理）。実データには「既に部分的に整列されている」場合があり、このとき高速化できる。
- ガロッピング（galloping）：Timsort（PythonやJavaで使われるハイブリッドソート）が採用する技法で、片方のブロックから連続して要素を取るべきときに二分検索でまとめて移動するなどの工夫を行い高速化する。
合併ソートが向く場面・向かない場面
- 向く場面: 大きなデータや外部ストレージ上のデータ、安定性が必要な場合、最悪ケースでも O(n log n) を保証したい場合。
- 向かない場面: メモリが非常に限られている環境（ただしリンクリストならOK）、実装の定数因子が気になる場合（イントロソートやクイックソートは平均的に高速なことが多い）。
ステップ例（小さな配列での動作）
配列 [5, 2, 4, 7, 1, 3, 2, 6] をソートする過程（概略）：
- 分割: [5,2,4,7] と [1,3,2,6]
- さらに分割: [5,2] [4,7] / [1,3] [2,6]
- 単位まで分割: [5] [2] [4] [7] [1] [3] [2] [6]
- マージ: [2,5] [4,7] → [2,4,5,7] ／ [1,3] [2,6] → [1,2,3,6]
- 最終マージ: [2,4,5,7] と [1,2,3,6] をマージして [1,2,2,3,4,5,6,7]
実装上の注意点
- 再帰深度: 再帰版は深さが log n だが、言語のスタック制限に注意（非常に大きな n の場合）。
- 安定性を意図する場合は比較演算で等価時に左側優先にすること。
- メモリの使い方: 毎回新しい配列を確保すると断片化やオーバーヘッドが出るため、バッファの再利用を検討する。
- 並列実装時はマージ段階の負荷分散やメモリ競合に注意。
まとめ
合併ソートは理論的に堅牢で安定なアルゴリズムであり、外部ソートや安定性が必要な場面で特に有用です。一方で追加の作業領域を必要とするため、メモリ制約が厳しい場面では注意が必要です。実務では合併ソートそのものだけでなく、Timsort のような合併ソートに挿入ソートや適応的最適化を組み合わせたアルゴリズムがよく使われています。実装時はバッファの再利用や小さな部分列での切替えなど、定数因子の最適化を行うと実性能が大きく改善します。
参考文献
- マージソート - Wikipedia（日本語）
- Merge Sort — GeeksforGeeks（英語）
- std::stable_sort — cppreference.com（英語）
- Timsort - Wikipedia（日本語）
- 外部ソート - Wikipedia（日本語）
- Master theorem — Wikipedia（英語）
投稿者プロフィール
