マージソート、名前からして強そうだけど「分割して…再帰して…最後にマージ？」で脳が停止しがちですよね。
しかも計算量の話が出てくると、更に置いていかれる感じ。
この記事は**“マージ（合体）こそ本体”**という視点で、初心者がつまずくポイントを先回りしながら、図解→実装→使いどころまで一気に整理します。
1. 学ぶ前に押さえる前提
1-1. ソートと安定性の超基本
1-1-1. 安定ソートが必要になる場面
まず「ソート」は、データを決まったルールで並べる事です。
例えば「小さい順」「名前のあいうえお順」みたいな並べ替えです。 (ウィキペディア)
ここで大事なのが 安定（あんてい）ソート。
安定ソートとは、同じ値（同じキー）の物同士の“元の順番”を守って並べ替えるソートの事です。 (EverPlay（エバープレイ）)
例えば、こんな名簿があるとします。
- 田中（A組）
- 佐藤（B組）
- 鈴木（A組）
- 高橋（B組）
ここで「組」で並べ替えると、A組→B組に並びます。
でも A組の中で「田中→鈴木」という元の順番がそのまま残るのが「安定」です。 (EverPlay（エバープレイ）)
これが何に役立つかというと、2回ソートしたい時です。
例：
1回目：入学した日付順（古い→新しい）
2回目：クラス順（A→B→C）
このとき、2回目を安定ソートでやれば、**クラスごとに“入学日順が崩れない”**状態になります。
だから「データの意味を壊さずに並べ替えたい」場面で安定ソートは強いです。 (EverPlay（エバープレイ）)
そしてマージソートは、作り方次第で 安定に出来るのが大きなポイントです。 (ウィキペディア)
2. マージソートの全体像
2-1. 分割→整列→マージの流れ
2-1-1. 例で追う：8要素を分けて戻す
マージソートは、ざっくり言うとこうです。
- 配列を半分に分ける
- さらに半分に分ける
- 1個ずつになったら「もう整列済み」と考える
- 2つずつくっつけて（マージして）整列済みの大きい配列にする
- それを繰り返して、最後に全体が整列する
この「分けて、後でくっつける」考え方を 分割統治と言います。 (Qiita)
例：[8, 4, 5, 2, 9, 1, 7, 3]
分ける（イメージ）：
[8,4,5,2,9,1,7,3]
→ [8,4,5,2] + [9,1,7,3]
→ [8,4] + [5,2] + [9,1] + [7,3]
→ [8]+[4]+[5]+[2]+[9]+[1]+[7]+[3]
ここまで来たら、1個の配列は必ず整列しています（だって1個だから）。
次に「くっつける」：
[8]と[4]を比べて →[4,8][5]と[2]→[2,5][9]と[1]→[1,9][7]と[3]→[3,7]
さらに
[4,8]と[2,5]→[2,4,5,8][1,9]と[3,7]→[1,3,7,9]
最後に
[2,4,5,8]と[1,3,7,9]→ 完成！
この時本当に大事なのは、「分ける」より **“くっつける（マージ）”**です。
マージが出来るようになると、マージソート全体が分かってきます。 (東京学芸大学)
3. 一番大事な「マージ処理」
3-1. 2つの整列済みリストを併合
3-1-1. 「<=」か「<」かで安定性が変わる
マージとは、既に並んでいる2つの列を、もう一回綺麗に1本にする作業です。 (東京学芸大学)
コツは「先頭同士を見て、小さい方を先に出す」を繰り返すだけ。
例：
左：[2, 5, 8]
右：[3, 5, 7]
- 2と3 → 2を出す
- 5と3 → 3を出す
- 5と5 → どっちを先に出す？
ここがポイントです。
同じ（5と5）なら 左を先に出すと、元の順番を守りやすくなり、安定になります。 (IT用語辞書)
だから、実装ではよくこう書きます。
if L[i] <= R[j]:
# 同じなら左を先に
もし < にしてしまうと、「同じだったら右が先に出る」事が起きて、安定じゃなくなる場合があります（同値の順番が入れ替わる）。 (IT用語辞書)
マージソートを理解する最短ルートは、ここを覚える事です。
「左右を比べて、小さい方を取る。等しいときは左を取る」
これが出来たら、後はそれを何回もやっているだけです。 (東京学芸大学)
4. 再帰で書くマージソート（Python）
4-1. 最小構成の実装
4-1-1. 補助配列でバグを減らすコツ
初心者がつまずきやすいのは **再帰（さいき：自分をもう一回呼ぶ）**です。
でも、形を決めてしまえばそんなに怖くないです。
安全な作り方はこう：
- 「いま見ている範囲」を
[l, r)（l以上、r未満）で表す - 要素が1個以下なら終わり（これが止まる条件）
- 真ん中
mで分けて、左と右をそれぞれ整列 - 最後にマージ
そして、マージの時に **補助配列（作業用の配列）**を使うと、混乱が減ります。
「一旦作業用に並べてから、元に戻す」感じです。 (Qiita)
易しめ実装（説明用）：
def merge_sort(a):
work = [0] * len(a)
def sort(l, r):
if r - l <= 1: # 1個以下なら終わり
return
m = (l + r) // 2
sort(l, m) # 左を整列
sort(m, r) # 右を整列
# ここからマージ（左右は整列済み）
i, j, k = l, m, l
while i < m and j < r:
if a[i] <= a[j]: # 同じなら左→安定
work[k] = a[i]; i += 1
else:
work[k] = a[j]; j += 1
k += 1
while i < m:
work[k] = a[i]; i += 1; k += 1
while j < r:
work[k] = a[j]; j += 1; k += 1
a[l:r] = work[l:r] # 元に戻す
sort(0, len(a))
return a
この形だと「どこを見ているか」がはっきりします。
初心者はまずこれをそのまま写して動かして、次に自分で少しずつ変えると理解が速いです。 (ウィキブックス)
5. 再帰が苦手ならボトムアップ
5-1. 反復（iterative）版の考え方
5-1-1. 1,2,4…と幅を倍にしてマージ
再帰がどうしても苦手なら、再帰を使わないマージソートがあります。
それが **ボトムアップ（下から積む）**の考え方です。 (EverPlay（エバープレイ）)
イメージはこうです。
- 最初は「長さ1の整列済みの塊」が沢山あると思う
- 隣り同士をマージして「長さ2の整列済み」にする
- 次は長さ2同士をマージして「長さ4」にする
- 次は8…と倍々で広げる
だから「1,2,4,8…」と幅（width）が増えていきます。 (EverPlay（エバープレイ）)
この方法は、再帰を使わないので頭がスッキリしやすいです。
更に、現実のデータは「ちょっと並んでる」事が多いので、そういう性質をうまく使う TimSortみたいな仕組みもあります（PythonのsortはTimSort）。 (Python documentation)
6. 計算量とメモリの腹落ち
6-1. なぜO(n log n)なの？
6-1-1. 深さlog n × 各層O(n)のイメージ
「O(n log n)って何？」を、数学をなるべく使わずに言うとこうです。
- 半分に分ける回数は、だいたい log n 回
（8個→4→2→1 みたいに、半分にできる回数） (TUKUMO工房 – 自作ツールと技術メモで「面倒」を「便利」に変える場所) - マージは、毎回ぜんぶの要素を一度は見るので、1回の段（層）あたり n くらいの手間 (Qiita)
だから
（段の数）log n ×（1段の手間）n = n log n
という感じです。 (Qiita)
もう1つ大事なのがメモリ。
マージソートは、作業用の配列を使うことが多いので、追加で 大体n個分の場所が必要になります（O(n)）。 (ウィキペディア)
まとめると：
- 速さ：だいたいO(n log n)で安定
- ただし：メモリは多めに使いがち
この「いい所・弱い所」をセットで覚えると、実際に使う場面が見えてきます。 (ウィキペディア)
7. いつ使う？他ソートとの比較
7-1. クイック／ヒープと比べる
7-1-1. 最悪ケース保証と安定性の価値
「マージソートって、いつ使うの？」は良くある疑問です。
答えはシンプルで、次の2つを大事にしたい時です。
① 最悪でもそこそこ速いのがいい
マージソートは、データの並び方にあまり左右されにくく、安定してO(n log n)の感じになりやすいです。 (ウィキペディア)
（クイックソートは平均的に速いけど、実装や状況で一気に遅くなる話が出ます。だから「最悪を踏みたくない」ならマージソートが安心、という考え方になります。）
② 同じ値の順番（安定性）を守りたい
名簿や表データみたいに「同じ点数の人が多い」とか、「2回ソートしたい」みたいな場面では、安定性が効きます。 (EverPlay（エバープレイ）)
逆に、メモリが厳しいなら、別の方法（ヒープソートなど）を選ぶ事もあります。
大事なのは「どれが一番」ではなく、目的に合うかです。 (ウィキブックス)
8. 練習問題と次の一歩
8-1. 手を動かして定着させる
8-1-1. 転倒数・stable_sortでレベルアップ
マージソートは、理解したつもりでも、手を動かすと穴が見つかります。
お勧めの練習はこの順番です。
ステップ1：まず普通にソート出来るようにする
自作のマージソートを動かして、色んな配列で試します。
- 既に並んでいる
- 逆順
- 同じ数字が沢山
- 1個、2個、3個…（小さい入力）
こういうテストをすると、境界ミスに気づきます。
ステップ2：転倒数を数えてみる
転倒数は「本当はこっちが先なのに、逆になってるペアの数」です。
例：[3, 1, 2] だと
(3,1) と (3,2) が逆なので転倒数は2です。
これ、マージの途中で数えられます。
マージ中に「右の要素の方が小さいから先に取る」場面があると、左に残っている要素の数だけ「逆のペア」が増える、という考え方です。 (プログラミング原人の進化論)
転倒数はアルゴリズム問題でも良く出るので、ここまで出来ると一気に強くなります。 (ITエンジニア向け転職・就活・学習サービス〖paiza〗)
ステップ3：標準ソートも観察してみる（安定性）
Pythonの sort や sorted は TimSortで、安定で、複数キーのソートにも向いています。 (Python documentation)
「自作」→「標準は何してる？」まで行くと、勉強が実用に近付きます。
まとめ
マージソートは、**「分ける → それぞれを整える → くっつける（マージ）」**で並べ替える方法です。
まず配列をどんどん半分に分けて、1個になったらそれはもう並んでいると考えます。
後は、並んだ2つの列を、先頭同士を比べながら小さい順に合体していき、最後に全体が綺麗に並びます。 (ウィキペディア)
マージソートの良い所は、主に2つです。
- 速さが安定しやすい：大体 O(n log n) の計算量で、極端に遅くなりにくいのが強みです。 (ウィキペディア)
- 安定ソートにしやすい：多くの実装では、同じ値同士の元の順番を保ったまま並べ替えできます（＝安定）。 (ウィキペディア)
一方で注意点もあります。配列でマージソートを作ると、マージする時に作業場所（別の配列）を使う事が多く、追加でO(n)位のメモリが必要になりがちです。 (ウィキペディア)
また、実務や学習では「安定性」を知っておくと便利です。例えばPythonの sorted() や list.sort() は、**同じキーの要素の順番を保つ（安定）**ことが保証されています。
だから「部署で並べてから年齢で並べる」など、複数回の並べ替えもやりやすいです。 (Python documentation)
最後に一言。
マージソートを理解するコツは、分け方よりも **「マージ（合体）の仕組み」**をしっかり押さえる事です。
マージが分かれば、全体の流れも自然に理解出来るようになります。 (ウィキペディア)
コメント