マージソート
マージソート
このレッスンで分かること
マージソート (merge sort)は 分割統治法 (divide and conquer) の代表例で、計算量O(n log n)を保証する強力なアルゴリズムです- 配列のサイズが
1まで小さくなれば、それは自明にソート済みです[6, 3, 8, 5, 2, 7, 1, 4]をマージソートする様子を図で見ます
マージソート とは
配列を半分に分割しては結合するマージソートを実装し、分割統治法と O(n log n) の世界を体感する。
マージソート (merge sort) は 分割統治法 (divide and conquer) の代表例で、計算量 O(n log n) を保証する強力なアルゴリズムです。発想は単純で、「配列を半分に割って、それぞれをソートし、ソート済みの 2 つを マージ する」を再帰的に繰り返します。
配列のサイズが 1 まで小さくなれば、それは自明にソート済みです。あとは戻り際に 小さいほうから順に取り出して並べる だけ。大きな問題を小さな問題に分割するこの考え方は、後で出てくる クイックソート や 二分探索 にも通じます。
マージソートは
O(n log n)を保証する安定ソート。ただしO(n)の追加メモリが必要。
アルゴリズムの動き
[6, 3, 8, 5, 2, 7, 1, 4] をマージソートする様子を図で見ます。
図のポイント (テキスト併記)
- 下から上へ戻りながら、2 つのソート済み列を 1 つにマージしていきます
下から上へ戻りながら、2 つのソート済み列を 1 つにマージしていきます。マージ自体は O(n) の作業で、再帰の深さが log n なので全体で O(n log n)。
マージのコア処理
2 つのソート済み配列をマージするには、それぞれの先頭から見比べて小さいほうを取っていくだけです。
Python
def _merge(left, right):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return mergedどちらかを使い切ったら、残りをそのまま末尾に付け足すのを忘れずに。<= (等号入り) にしておくと 安定ソート になります。
マージソート本体
Python
def mergeSort(arr):
if len(arr) <= 1:
return list(arr)
mid = len(arr) // 2
left = mergeSort(arr[:mid])
right = mergeSort(arr[mid:])
return _merge(left, right)再帰の停止条件は「要素 1 個以下なら自分自身を返す」。中央で割って左右をそれぞれ再帰的にソートしてから _merge で結合します。
JavaScript での実装
JavaScript
function mergeSort(arr) {
if (arr.length <= 1) return [...arr];
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const merged = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) merged.push(left[i++]);
else merged.push(right[j++]);
}
return merged.concat(left.slice(i)).concat(right.slice(j));
}計算量メモ
- 時間計算量: 最良 / 平均 / 最悪 すべて
O(n log n) - 空間計算量:
O(n)(マージで一時配列が必要) - 安定:
はい - in-place:
いいえ
クイックソートは平均O(n log n)だが最悪O(n^2)。マージソートは 常にO(n log n)を保証する。
よくある間違い
1 つ目は 停止条件のミス。len(arr) == 0 だけだと長さ 1 の配列で無限再帰します。<= 1 にしておくのが安心。2 つ目は mid の計算。整数除算 // (Python) や Math.floor を忘れて浮動小数で割り、arr.slice(2.5) のような変な呼び出しになることがあります。3 つ目は マージ後の残り処理忘れ。while ループを抜けた後の left[i:] / right[j:] を append しないと、要素が消えます。
やってみよう
[6, 3, 8, 5, 2, 7, 1, 4]を入れて、各ステップでどの 2 列がマージされているか手で追ってみる。<(等号なし) にすると安定性が崩れることを、[(1, 'a'), (1, 'b')]のようなタプル配列で確認する。- 再帰なしの ボトムアップ版 (反復で要素 1 -> 2 -> 4 -> ... と統合) を書いてみる。
外部マージソート
メモリに収まらない巨大データ (例えば 100GB のログファイル) をソートする場合、外部マージソート が定番の選択肢です。手順は次の通り。
- データを分割してメモリに収まる単位 (例
1GBずつ) でソートし、一時ファイルとして保存 - すべての一時ファイルを 同時に 先頭から読みつつマージ (k-way merge)
- マージ結果を最終ファイルへ書き出す
図のポイント (テキスト併記)
- データベースの
ORDER BYやMapReduceのシャッフルフェーズも、この外部マージソートと同じ考え方で動いています
データベースの ORDER BY や MapReduce のシャッフルフェーズも、この外部マージソートと同じ考え方で動いています。
マージソートは シーケンシャルアクセス に強い。HDD やテープのような順次読み込みデバイスでも効率的に動く。
よくある質問
Q. このトピックは実務でどう役立ちますか？
A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。
Q. 計算量はどう求めれば良いですか？
A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。
Q. 覚えるべき定番アルゴリズムは何ですか？
A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。
次のレッスン
次は クイックソート で、ピボットを基準に配列を分割して並べ替える別の分割統治アルゴリズムを学びます。マージソートとの計算量・メモリ特性の違いにも注目してみてください。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- マージソート の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. マージソート とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 組み込みのソート関数 (Python の sorted, JS の sort, Go の sort.Slice) は使わない
- 配列を半分に分割して再帰し、ソート済みの 2 列をマージする分割統治法で実装する
- 戻り値は新しい配列で、入力 arr を破壊的に書き換えない
入出力例
test-cases.txt
mergeSort([6,3,8,5,2,7,1,4]) → [1,2,3,4,5,6,7,8]
mergeSort([1,2,3,4,5]) → [1,2,3,4,5]
mergeSort([5,4,3,2,1]) → [1,2,3,4,5]
mergeSort([3,1,3,2,1]) → [1,1,2,3,3]
mergeSort([99]) → [99]
mergeSort([2,1]) → [1,2]
mergeSort([-3,5,-1,0,2,-7]) → [-7,-3,-1,0,2,5]