マージソートの計算量の導出を簡易的に行う記事です
「マージソートって $O(N log N)$ らしいけど、
なぜそうなるのかを “自分の言葉で説明できるか？” と聞かれると、ちょっと自信がない。
そんな人のための記事です。
私自身、マージソートの仕組みを見て、「対数と何の関連性があるんだ？」と疑問に思い気になって仕方がなくなったので、平易な数学を用いて導出したいと思います。
マージ操作（merge）をまず理解しよう
マージソートの “核” は マージ（merge）操作 です。
これは 「ソート済みの2つの配列を、1つのソート済み配列に結合する処理」 のこと。
ここさえ理解すれば、マージソートへの理解が半分終わったようなものです。
マージ操作の直感的なイメージ
2 つのソート済み配列 A [1,3] と B [2,4]があるとします。
目標はこの二つの配列を合併して、新たなソートされた配列[1,2,3,4]を作ることです。
やることはシンプルで、
- A の先頭と B の先頭（各配列の最小要素）を比べる
- 小さい方を結果配列に入れる
- その配列のポインタを1つ進める
- どちらかが尽きるまで繰り返す
- 残った方を全部くっつける
これだけです。
実際の手順の図（イメージ）
まずは。Aの先頭の要素である１と２を比べます。
比べて小さい方の１を合併後の配列の先頭に入れます。
次に、残った[3]と[2,4]で再度先頭要素を比べます。
比べて小さい方の２を合併後の配列に追加します。
これを続けていくと最終的にソートされた合併後の配列[1,2,3,4]が得られることは理解できると思います。
マージソートとは何か（全体像をつかむ）
マージソート（Merge Sort）は
「分割して、並べて、マージする」 というシンプルな戦略を持つソートアルゴリズムです。
ポイントはこの 3 つ：
- 配列を半分に 分割
- 小さく分割した配列をそれぞれ 再帰的にソート
- ソート済みの2つの配列を マージ操作 する
といった流れになります。
全体の流れを直感で理解する
半分に分割したものを再帰的にソートするので、半分に分割する行為を繰り返していきます。
最終的に一つずつの配列になったものを、どんどんマージ操作していくイメージです。
では、次はこれを実際に数式に落とし込んでいきましょう。
全体の流れを数式で理解する
まず、ソートしたい配列の要素数を$N=2^k$(今回は簡易的に導出するため）とし、計算回数を求めます。
- 配列を半分に 分割
- 小さく分割した配列をそれぞれ 再帰的にソート
- ソート済みの2つの配列を マージ操作 する
この操作をその配列に行なっていきます。
半分にする分割回数は要素数が$2^k$であるため、$k$回です。(e.g., $4=2^2$は分割回数2回
分割した配列に対してマージ操作を行う際の比較回数は、すべて$N$回以下になります。これは分割した配列の要素数が$N$より大きいことが無いことから簡単に分かります。
$N=2^3=8$の例で見ると、分割回数は3回で各レイヤーの比較回数は8回以下なので、ざっくり計算量は$3*8$に抑えられることが分かるでしょう。
したがって、これを$N=2^k$に一般化すれば計算回数は
\begin{align}
Nk=NlogN
\end{align}
\begin{align}
k = \log_2 N⇔N=2^k
\end{align}
よって、欲しかった式を導出することができました。
まとめ（結論）
マージソートの計算量は $O(NlogN)$。
というのも、マージソートを二つの工程で分けると、
-
配列の分割は $log N$ 回
- 半分 → 半分 → 半分… と再帰的に分割していくため
- 分割の深さ（再帰の深さ）は $log_2 N$
-
各階層のマージ処理は合計で常に $N以下$
- 同じ階層の部分配列で、マージ操作する回数は$N$以下
- つまりどの階層でも作業量は $O(N)$で抑えられる
したがって、
\begin{align}
O(NlogN)
\end{align}
という計算量になります。