マージソート完全ガイド：仕組み・計算量・実装例と実務で使える最適化

2025年11月18日 最終更新日時 : 2025年11月18日 エバープレイ編集部

マージソートとは

マージソート（Merge Sort）は、分割統治法（divide and conquer）を用いる比較ベースのソートアルゴリズムの一つです。配列やリストを半分に分割してそれぞれを再帰的にソートし、最後に二つのソート済み部分列を線形時間で「マージ（併合）」することで全体を整列します。最悪・平均・最良いずれのケースでも時間計算量がΘ(n log n)である点、そして安定なソートが実現できる点が主要な特徴です。

アルゴリズムの概要（分割→統治→併合）

  • 分割（Divide）：対象配列をほぼ等しい二つの部分配列に分割する。
  • 統治（Conquer）：各部分配列を再帰的にソートする。要素数が1以下なら既に整列済みとして終了。
  • 併合（Combine / Merge）：二つのソート済み部分配列を、先頭から要素を比較して小さい方を順に取り出すことで一つのソート済み配列に合成する（この処理は線形時間で完了する）。

擬似コード（トップダウン版）

以下は典型的な再帰実装の擬似コードです。実装は配列と補助配列を使うのが一般的です。

merge_sort(A, left, right):
  if left >= right: return
  mid = (left + right) // 2
  merge_sort(A, left, mid)
  merge_sort(A, mid+1, right)
  merge(A, left, mid, right)

merge(A, left, mid, right):
  create temporary array T
  i = left; j = mid+1; k = 0
  while i <= mid and j <= right:
    if A[i] <= A[j]:
      T[k++] = A[i++]
    else:
      T[k++] = A[j++]
  copy remaining elements from left or right half into T
  copy T back into A[left..right]

配列での具体例

配列 [5, 2, 4, 7, 1, 3, 2, 6] をマージソートすると、まず半分に分けてそれぞれを再帰的にソートし、最終的に次のような併合を行います（段階的に）:

  • [5,2,4,7] と [1,3,2,6] に分割
  • [5,2] [4,7] ... とさらに分割し、最小単位の長さ1まで細分化
  • 長さ1のペアをマージして長さ2、長さ4と統合していき、最終的に長さ8の整列済み配列 [1,2,2,3,4,5,6,7] が得られる

計算量

  • 時間計算量（比較回数）: 最悪・平均・最良のすべてで Θ(n log n)。これは分割回数が log n、各レベルでのマージ処理が合計でΘ(n)だからです。
  • 空間計算量: 通常は補助配列を使うため追加で O(n) の補助領域が必要です。連結リストで実装する場合は O(1) の追加領域で実現可能（ポインタ操作によるマージ）。
  • 安定性: 標準的なマージ処理は安定（等しいキーの相対順序を保つ）です。

特徴と利点・欠点

  • 利点
    • 安定で予測可能なΘ(n log n)の実行時間
    • 外部ソート（ディスク上の大規模データ）の基本的手法である k-way マージに拡張可能
    • 連結リストへの適用では O(1) の追加メモリで簡潔に実装できる
    • 並列化しやすい（左右部分の独立実行とマージの並列化が可能）
  • 欠点
    • 配列実装では補助配列分の追加メモリが必要（インプレース実装は理論上可能だが複雑で実用性に欠ける）
    • 小さい配列やメモリ制約が厳しい環境では、挿入ソートなどより高速な選択肢がある場合がある

最適化と変種

  • ボトムアップ（反復）マージソート: 再帰を使わず、長さ1,2,4,... と段階的にマージしていく方式。実装がループ中心でスタック使用を避けられる。
  • 自然マージソート（Natural Merge Sort）: 既に連続している昇順の「ラン（run）」を検出し、それらをマージしていく。データに既存の順序がある場合に高速化される。
  • 小さい部分は挿入ソートで処理: 再帰を一定の深さで止め、底辺の小さい配列を挿入ソートで整列すると実行定数が改善されることが多い。
  • Timsort: Python や Java の一部実装で使われる、自然マージと挿入ソート、"galloping" と呼ばれる高速合流を組み合わせた現代的ソート。実データに強く最適化されている。
  • 外部ソートへの応用: データがメモリに収まらない場合、ディスク上のチャンクをソートして k-way マージで統合するアルゴリズムの基礎となる。

連結リストへの適用

連結リストではマージ操作はポインタのつなぎ替えで行えるため、追加配列を必要とせず O(1) の追加メモリで安定なソートが可能です。分割は快適に行うために「遅速ポインタ」手法（fast/slow pointer）で中央を見つけるのが一般的です。

実務上の注意点

  • 配列での大規模データ処理では補助配列分のメモリがボトルネックになる可能性がある。外部ソートや分割配置、メモリ節約型実装を検討する。
  • 小さな配列や部分配列では挿入ソートの方が速い場合が多い。実装時にはしばしば閾値を設ける。
  • キャッシュ局所性: 単一大配列に対するマージはメモリアクセスパターンによってはキャッシュ効率が良くないことがある。底アップやチューニングで改善可能。
  • 並列処理: マルチコア環境では左右の再帰処理を並列化し、マージを分割して並列に実行することで加速できる。ただしメモリ帯域や同期コストに注意。

クイックソート等との比較

  • クイックソートは平均で O(n log n) だが最悪 O(n^2)（ピボット選び次第）。実行定数が小さく実装によっては速いが、安定性は保証されない（特別な実装を除く）。
  • ヒープソートは O(n log n) の時間と O(1) の追加メモリだが、安定性がない。実行定数は大きめ。
  • マージソートは安定性と最悪計算量の保証が必要な場面（安定性要求、外部ソート、大規模データ）で有利。

まとめ

マージソートは分割統治法に基づく安定で予測可能なソートアルゴリズムです。配列実装では追加で O(n) のメモリを必要としますが、時間計算量は常に Θ(n log n) で安定性があり、外部ソートや連結リストのソート、並列処理に適しています。実装上は底アップ、自然マージ、閾値以下での挿入ソート併用など現実的な最適化を組み合わせることで性能向上が期待できます。

参考文献

カテゴリー
IT
前の記事
Dexys Midnight Runners完全ガイド：ケヴィン・ローランド、代表曲・名盤・聴きどころNew!!
2025年11月18日
次の記事
Echo & the Bunnymen完全ガイド：プロフィール・名盤・代表曲と今聴くべき理由New!!
2025年11月18日