ソートアルゴリズムの中でも、特に信頼性が高く広く使われているのがマージソートです。
マージソートは分割統治法をベースにした安定ソートであり、最悪ケースでもO(n log n)という優れた時間計算量を保証します。
本記事では、マージソートの計算量（時間計算量・空間計算量）について詳しく解説するとともに、分割統治の仕組み・安定ソートとしての特性・外部ソートへの応用についても丁寧に説明します。
「なぜO(n log n)なのか」という理論的な背景から、実際の実装例まで幅広くカバーしていますので、ぜひ参考にしてみてください。
マージソートの計算量はO(n log n)（結論）
それではまず、マージソートの計算量がO(n log n)である理由について解説していきます。
マージソートは「配列を半分に分割する」操作と「2つのソート済み配列をマージ（統合）する」操作の組み合わせで動作します。
分割フェーズでは、n個の要素を持つ配列を再帰的に半分ずつ分割します。
配列を1要素になるまで分割するには、log₂(n)回の分割が必要です。
マージフェーズでは、各レベルで合計n個の要素を1回ずつ処理するため、各レベルのコストはO(n)です。
レベル数はlog₂(n)なので、全体の時間計算量はO(n) × O(log n) = O(n log n)となります。
マージソートの重要な特徴は、最良・平均・最悪のすべてのケースでO(n log n)が保証されることです。クイックソートは平均O(n log n)ですが最悪O(n²)になる可能性があるため、最悪ケースの保証が必要なシステムではマージソートが優先されます。
漸化式によるO(n log n)の導出
マージソートの計算量はマスター定理を使って厳密に導出できます。
T(n) = 2T(n/2) + O(n)
（左半分をソート：T(n/2)、右半分をソート：T(n/2)、マージ：O(n)）
マスター定理（ケース2）を適用：T(n) = O(n log n)
この漸化式は「サイズnの問題を、サイズn/2の2つの部分問題に分割し、O(n)の追加コストで解く」ことを表しています。
マスター定理により、このパターンはO(n log n)と解析されます。
空間計算量はO(n)
マージソートの空間計算量はO(n)です。
これは、2つの部分配列をマージする際に一時的な作業用配列が必要なためです。
n個の要素を持つ配列をソートする場合、最大でn個の要素を格納できる補助領域が必要になります。
この点がin-place（その場ソート）なヒープソートや挿入ソートと異なる部分です。
O(n)の空間コストを許容できない環境では、別のアルゴリズムを検討する必要があるでしょう。
ソートの計算量下界との関係
比較ベースのソートアルゴリズムには、計算量の理論的下界がO(n log n)であることが証明されています。
これは情報理論的な議論に基づいており、n個の要素を並べる順列の数はn!通りあり、それを二分木で識別するには少なくともlog₂(n!) ≒ n log n回の比較が必要というものです。
マージソートはこの理論的な下界に到達しているため、比較ベースのソートとして最適なアルゴリズムの一つと言えます。
マージソートの仕組みと実装
続いては、マージソートの具体的な仕組みと実装方法を確認していきます。
マージソートの処理は大きく「分割（Divide）」と「マージ（Merge）」の2つのフェーズに分かれます。
分割フェーズの仕組み
分割フェーズでは、配列を中央で左右の2つに分割し、各部分をさらに再帰的に分割します。
この処理は要素数が1になるまで繰り返されます。
要素数1の配列はそれ自体がソート済みであるため、再帰の基底ケースとなります。
例：配列 [5, 2, 8, 1, 9, 3] の分割
[5, 2, 8, 1, 9, 3]
→ [5, 2, 8] と 
→ [5, 2] [8] と 
→ [5] 
[8] と [9]
（すべて1要素になった）
マージフェーズの仕組み
マージフェーズでは、2つのソート済み部分配列を1つのソート済み配列に統合します。
先頭から小さい方の要素を順番に取り出して新しい配列に格納する、というシンプルな操作です。
例： と のマージ
比較①：2 vs 1 → 1を取得 →
比較②：2 vs 4 → 2を取得 →
比較③：5 vs 4 → 4を取得 →
残り5を追加 →
2つの配列の要素数をm, nとすると、マージに必要な比較回数は最大m+n-1回であり、O(m+n)です。
Pythonでの実装例
マージソートのPython実装を示します。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
このコードはシンプルですが、O(n)の補助配列を使用するため空間計算量はO(n)です。
安定ソートとしての特性と外部ソートへの応用
続いては、マージソートが安定ソートであることの意味と、外部ソートへの応用について確認していきます。
安定ソートとは何か
安定ソートとは、同じキー値を持つ要素の相対的な順序がソート前後で変わらないソートアルゴリズムのことです。
たとえば「田中・28歳」「山田・28歳」という2つのレコードが元々この順序で並んでいた場合、年齢でソートしても「田中→山田」の順序が維持されるのが安定ソートです。
| アルゴリズム | 安定性 | 時間計算量（最悪） | 空間計算量 |
|---|---|---|---|
| マージソート | 安定 | O(n log n) | O(n) |
| クイックソート | 不安定 | O(n²) | O(log n) |
| ヒープソート | 不安定 | O(n log n) | O(1) |
| 挿入ソート | 安定 | O(n²) | O(1) |
| バブルソート | 安定 | O(n²) | O(1) |
マージソートは安定ソートであるため、データベースのソート操作や複数キーを使った複合ソートに特に適しています。
安定ソートの重要性
安定ソートが必要になる典型的な場面として、スプレッドシートやデータベースの「複数列ソート」があります。
まず「部署」でソートし、次に「年齢」でソートしたい場合、2回目のソートが安定でなければ1回目のソート結果が壊れてしまいます。
安定ソートを使えば、複数のキーを順番に適用するだけで正しい複合ソートが実現できます。
Pythonのsort()やJavaのCollections.sort()がマージソート系（Timsort）を採用しているのも、安定性が求められるためです。
外部ソートとしての応用
外部ソートとは、メモリに収まりきらない大容量データをディスクなどの外部記憶装置を使ってソートする手法です。
マージソートは外部ソートに最適なアルゴリズムとして知られています。
その理由は、マージソートがデータを「分割→個別にソート→マージ」するプロセスをとるため、一度にメモリに読み込むデータ量を制限しながら処理できるからです。
外部マージソートの基本的な手順は、①大きなファイルをメモリサイズに収まるチャンクに分割、②各チャンクをメモリ内でソート、③ソート済みチャンクをマージ、という3ステップです。この手法は大規模データ処理（Hadoop/MapReduceなど）の根幹にもなっています。
マージソートの実際の使用場面と他のソートとの比較
続いては、マージソートが実際に使われる場面と他のソートアルゴリズムとの使い分けについて確認していきます。
マージソートが選ばれる場面
マージソートが特に有効な場面として、まず「安定ソートが必要なとき」があります。
前述のように、安定性が求められるデータ処理ではマージソート系が優先されます。
次に「最悪計算量をO(n log n)に保証したいとき」があります。
クイックソートは平均的には高速ですが、特定の入力パターンで最悪O(n²)になる可能性があります。
セキュリティや信頼性が求められるシステムでは、最悪ケースが保証されるマージソートが適しています。
さらに「連結リストのソート」にも向いています。
連結リストはランダムアクセスが苦手なため、クイックソートより連結リストに適したマージソートが有利です。
クイックソートとの使い分け
クイックソートは平均O(n log n)でキャッシュ効率が高く、実測では多くの場面でマージソートより高速です。
しかし、最悪O(n²)のリスクがあるため、用途によって使い分けが必要です。
| 比較項目 | マージソート | クイックソート |
|---|---|---|
| 最悪時間計算量 | O(n log n) | O(n²) |
| 安定性 | 安定 | 不安定 |
| 空間計算量 | O(n) | O(log n) |
| キャッシュ効率 | やや低い | 高い |
| 得意なデータ構造 | 連結リスト・外部ソート | 配列 |
Timsortとの関係
現代のプログラミング言語では、マージソートを改良した「Timsort」が標準ソートアルゴリズムとして広く採用されています。
TimsortはPython（バージョン2.3以降）やJava（Java SE 7以降のArrays.sort）などで使われています。
Timsortは実データに多く見られる「部分的に整列済みのデータ」に対して特に効率的で、最良ケースはO(n)、最悪ケースもO(n log n)という優れた特性を持ちます。
マージソートの考え方は現代の高度なソートアルゴリズムにも受け継がれています。
まとめ
マージソートの時間計算量はO(n log n)であり、最良・平均・最悪のすべてのケースでこれが保証される信頼性の高いアルゴリズムです。
空間計算量はO(n)で、マージのための補助配列が必要です。
分割統治法をベースにしており、配列を再帰的に半分に分割し、ソート済みの部分配列を順次マージすることで全体をソートします。
安定ソートであるため、複合ソートや安定性が重要な場面で広く採用されています。
また外部ソートへの応用や、Timsortへの発展形など、実用的な価値が非常に高いアルゴリズムです。
ソートアルゴリズムの選択において、マージソートの特性を正しく理解することは非常に重要でしょう。
