マージソートとは（全体像）
マージソートとは、データを半分ずつに分けていき、小さくなったまとまりを並べ替えてから、合体（マージ）して、最後に1つの並んだ列にする方法のことだ。
トランプの山をイメージしよう。山を半分ずつに分け続け、小さい山を並べてから、合体していく。合体するときに、両方を見比べて、順番に並べていく。
ここで一番のポイント。マージソートの計算量は、常にO(n log n)。クイックソートは最悪のときO(n²)まで遅くなることがあるが、マージソートは、最悪のときでもO(n log n)が保証される。これが大きな強みだ。
詳しく：常にO(n log n)と、追加メモリ
ここが心臓部。マージソートのポイントを押さえよう。
マージソートのポイント
| 項目 | やさしい意味 |
|---|---|
| 方式 | 半分に分ける → 並べ替える → 合体（マージ）する |
| 計算量 | 常にO(n log n)（最悪のときでも保証される） |
| 追加メモリ | 合体（マージ）のために、追加のメモリが必要 |
| 向き | 大規模データ（メモリに収まらない場合）にも有利 |
マージソートの強みは、速さが常に保証されること。最悪のときでもO(n log n)なので、安定して速い。
ただし、注意点もある。合体（マージ）のときに、作業用の追加メモリが必要だ。「マージソートは追加メモリが要らない」と思い込むと誤りになる。なお、大きすぎてメモリに収まらないデータの並べ替えにも向いている。
わかりやすく言い換えると
身近なたとえで整理しよう。
マージソートは、「トランプの山を半分ずつに分け続け、小さい山を並べてから、合体していく」イメージ。合体のとき、両方を見比べて順に並べる。
「常にO(n log n)」というのは、どんなデータでも、安定して速いこと。要するに、最悪のときでも遅くなりにくい。
「追加メモリが必要」というのは、合体のときに、作業用の場所がいること。つまり、メモリを少し多めに使う。
試験のツボ
🔴 一番出る：マージソートの仕組み
①半分に分けて、それぞれを並べ替え、合体（マージ）する
②合体のとき、両方を見比べて順に並べる
🔴 次に出る：常にO(n log n)
①計算量は、常にO(n log n)（最悪のときでも保証）
②クイックソートの最悪（O(n²)）より、保証の点で有利
🟡 押さえると安定：追加メモリ
①合体（マージ）のために、追加のメモリが必要
②大きすぎてメモリに収まらないデータにも向く
よくある間違い
①「マージソートは、最悪のときO(n²)まで遅くなる」→ ✗ マージソートは、常にO(n log n)。最悪のときでも速さが保証される。
②「マージソートは、追加のメモリがいっさい要らない」→ ✗ 合体（マージ）のために、作業用の追加メモリが必要。
③「マージソートは、隣り合うデータを比べて入れ替えるだけだ」→ ✗ 隣どうしを比べるのはバブルソート。マージソートは、分けて並べて合体する。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（マージソートの仕組み）
マージソートに関する次の記述のうち、最も適切なものはどれか。
- 半分に分けて並べ替え、合体（マージ）して並べ替える方法である
- 社員の出退勤を記録して、毎月の給与を計算していくしくみである
- 取引先へ毎月の請求書を郵送する、決まった事務作業である
- 完成したシステムを宣伝して、より多く売る広告活動である
解答は 1 だぱん。
マージソートは、半分に分けて並べ替え、合体（マージ）して並べ替える方法なんだぱん。トランプの山を分けて合体するイメージだぱん。
選択肢2は給与計算、選択肢3は請求書の事務、選択肢4は広告で、どれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 分けて並べ替え合体するで正しい |
| 2 | ✗ | 給与計算のしくみではない |
| 3 | ✗ | 請求書の事務の話 |
| 4 | ✗ | 広告活動ではない |
オリジナル問題2（常にO(n log n)）
マージソートの計算量に関する次の記述のうち、最も適切なものはどれか。
- 社員の給与の計算しだいで、計算量が決まるとされているものだ
- 取引先への請求書の枚数しだいで、計算量が決まるとされている
- 常にO(n log n)で、最悪のときでも速さが保証される
- 最悪のときは、必ずO(n²)まで遅くなるものだとされているものだ
解答は 3 だぱん。
マージソートは、常にO(n log n)で、最悪のときでも速さが保証されるんだぱん。これが大きな強みだぱん。
選択肢1の給与、選択肢2の請求書、選択肢4の「必ずO(n²)」は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算で決まるのではない |
| 2 | ✗ | 請求書の枚数で決まるのではない |
| 3 | ✓ | 常にO(n log n)で保証されるで正しい |
| 4 | ✗ | 最悪でもO(n log n)が保証される |
オリジナル問題3（追加メモリ）
マージソートのメモリに関する次の記述のうち、最も適切なものはどれか。
- 社員の給与を計算するメモリだけが必要だとされているものだ
- 取引先へ請求書を郵送するメモリだけが必要だとされている
- メモリは、いっさい使わずに並べ替えられるものだとされている
- 合体（マージ）のために、作業用の追加メモリが必要である
解答は 4 だぱん。
マージソートは、合体（マージ）のために、作業用の追加メモリが必要なんだぱん。「追加メモリが要らない」とまちがえないようにするといいぱん。
選択肢1の給与、選択肢2の請求書、選択肢3の「メモリを使わない」は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算のメモリではない |
| 2 | ✗ | 請求書のメモリではない |
| 3 | ✗ | 追加メモリが必要 |
| 4 | ✓ | マージ用の追加メモリが必要で正しい |
まとめ
押さえどころ
- 🔴 マージソート ＝ データを半分に分けて並べ替え、合体（マージ）して1つにする並べ替え方法。
- 🔴 常にO(n log n) ＝ 最悪のときでも速さが保証される。クイックソートの最悪（O(n²)）より、保証の点で有利。
- 🟡 追加メモリ ＝ 合体（マージ）のために、作業用の追加メモリが必要。大規模データにも向く。
次に学ぶ
- クイックソート ── 基準値で分ける並べ替え。マージソートと、速さの保証や仕組みを比べると分かりやすい。
- 計算量 ── アルゴリズムの速さの目安。最悪のときの保証も大切な見どころ。
執筆: SikakuQuest編集部