概要

配列のソートアルゴリズムの1つ。

アルゴリズム・具体例

元配列を分割

配列を同じ大きさに2分割（要素数が奇数の場合は1個差を許容）する操作を、要素数が1つになるまで繰り返す

       [2,5,6,3,1,0,4]
        /           \
    [2,5,6]       [3,1,0,4]
    /    \         /     \
  [2]  [5,6]    [3,1]   [0,4]
  /     / \      / \     / \
[2]   [5] [6]  [3] [1] [0] [4]

分割配列をソートしながらマージ

分割後の要素数1の配列は「ソート済みの配列」とみなせる。 これを逆方向にマージしつつ、正しい並び順になるように並び替える。

[2]   [5] [6]  [3] [1] [0] [4]
  \     \ /      \ /     \ /
  [2]  [5,6]    [1,3]   [0,4]
    \    /         \     /
    [2,5,6]       [0,1,3,4]
        \           /
       [0,1,2,3,4,5,6]

マージしたい2つのソート済み配列を $a={a_0, a_1, \cdots, a_{m-1}}, b={b_0, b_1, \cdots, b_{n-1}}$ とする。
配列 $a, b$ をマージするアルゴリズムは以下の通り。

  1. インデックスを格納する変数を初期化：$i, j \gets 0, 0$
  2. ソート済み配列を格納する空配列の変数 $c$ を宣言：$c \gets [\ ]$
  3. $i=m$ または $j=n$ となるまで以下の処理を繰り返す（= 小さいものから $c$ に詰め込む）
    1. $a_i, b_j$ の大きさを比較して、
      1. $a_i \le b_j$ の場合：$c$ 末尾に $a_i$ を追加し、$i$ をインクリメント（$i \gets i+1$）
      2. $a_i \gt b_j$ の場合：$c$ 末尾に $b_j$ を追加し、$j$ をインクリメント（$j \gets j+1$）
  4. $i,j$ の値に応じて以下の処理を実行（= 片方の配列の要素を使い果たしたので、もう一方の配列の残りの要素を $c$ に詰め込む）
    1. $i \lt m,\ j=n$ の場合：$c$ 末尾に $a_i, a_{i+1}, \cdots, a_{m-1}$ をこの順に追加
    2. $i=m,\ j\lt n$ の場合：$c$ 末尾に $b_j, b_{j+1}, \cdots, b_{n-1}$ をこの順に追加
    a:[2,5,6] b:[0,1,3,4] c:[]
       ^         ^
       i=0       j=0

a_i=2 > b_j=0 なので b_j を c に格納して j <- j+1

    a:[2,5,6] b:[0,1,3,4] c:[0]
       ^           ^
       i=0         j=1

a_i=2 > b_j=1 なので b_j を c に格納して j <- j+1

    a:[2,5,6] b:[0,1,3,4] c:[0,1]
       ^             ^
       i=0           j=2

a_i=2 < b_j=3 なので a_i を c に格納して i <- i+1

    a:[2,5,6] b:[0,1,3,4] c:[0,1,2]
         ^           ^
         i=0         j=2

a_i=5 > b_j=3 なので b_j を c に格納して j <- j+1

    a:[2,5,6] b:[0,1,3,4] c:[0,1,2,3]
         ^             ^
         i=0           j=3

a_i=5 > b_j=4 なので b_j を c に格納して j <- j+1

    a:[2,5,6] b:[0,1,3,4] c:[0,1,2,3,4]
         ^               ^
         i=0             j=4

配列 b のインデックス j が b の長さに等しくなったので、配列 a の残りの部分を c に追加

    c:[0,1,2,3,4,5,6]

--> ソート完了

計算量

時間計算量

  • 元配列の分割処理
    • 要素1つ1つを走査する必要はなく、真ん中で配列を分割するだけ
    • その分割ステップ数は $\log_2 n$ なので、計算量は $O(\log n)$
  • 分割配列のマージ処理
    • マージのステップが1回行われるごとに、配列の各要素が1回ずつ走査される
      • この計算量は $O(n)$
    • マージのステップ数は元配列の分割数と同じく $\log_2 n$
    • 以上により、マージ処理の計算量は $O(n\log n)$

以上より、マージソートの時間計算量は $O(\log n + n\log n) \sim O(n\log n)$

       [2,5,6,3,1,0,4]
        /           \           <-- split step 1
    [2,5,6]       [3,1,0,4]
    /    \         /     \      <-- split step 2
  [2]  [5,6]    [3,1]   [0,4]
  /     / \      / \     / \    <-- split step 3
[2]   [5] [6]  [3] [1] [0] [4]
  \     \ /      \ /     \ /    <-- merge step 1
  [2]  [5,6]    [1,3]   [0,4]
    \    /         \     /      <-- merge step 2
    [2,5,6]       [0,1,3,4]
        \           /           <-- merge step 3
       [0,1,2,3,4,5,6]

空間計算量

元配列に加えて、各ステップの分割配列のためのメモリが必要。
分割ステップ数は $\log n$ であり、各ステップごとに合計 $n$ 個の要素を格納する配列が必要になるので、空間計算量は $O(n \log n)$

実装

テスト：

>>> test_sort_algorithm(MergeSort())
OK: [1, 6, 2, 7, 5, 4, 3] --> [1 2 3 4 5 6 7]
OK: [2, 4, 3, 7, 6, 5, 1] --> [1 2 3 4 5 6 7]
OK: [3, 1, 5, 7, 6, 4, 2] --> [1 2 3 4 5 6 7]
OK: [3, 6, 5, 7, 4, 2, 1] --> [1 2 3 4 5 6 7]
OK: [4, 3, 7, 6, 5, 2, 1] --> [1 2 3 4 5 6 7]
OK: [5, 2, 1, 7, 6, 4, 3] --> [1 2 3 4 5 6 7]
OK: [5, 7, 2, 6, 4, 3, 1] --> [1 2 3 4 5 6 7]
OK: [6, 4, 3, 7, 5, 2, 1] --> [1 2 3 4 5 6 7]
OK: [7, 2, 5, 6, 4, 3, 1] --> [1 2 3 4 5 6 7]
OK: [7, 6, 5, 4, 3, 2, 1] --> [1 2 3 4 5 6 7]
All 5040 tests passed.

（参考）test_sort_algorithm：指定した長さの全ての組み合わせの配列を生成してソート結果をテストする関数

平均時間計算量 $O(n\log n)$ の確認：

Ns = np.arange(1, 20+1) * 1000
ave, std = experiment_computing_time(MergeSort(), Ns, T=10)
draw_computing_order(Ns, ave, std)

merge-sort

【NOTE】 綺麗に $n\log n$ にフィットせず若干波打って見えるのはなぜ？

（推測）以下のように実際の分割回数は整数なので、$\log_2 n$ とは完全には一致せず切り上げられる。そのため、実際の数値よりも理論値の方が小さくなる。

  • $n=4000$ のとき
    • $\log_2 n \simeq 11.97$
    • 実際に大きさ1の配列になるまでに必要な分割数は以下の通り12回
      • → 2000 → 1000 → 500 → 250 → 125
      • → 63 → 32 → 16 → 8 → 4
      • → 2 → 1
    • 実際の計算回数と理論値の差は $(11.97-12)/12 = -0.25$ %
  • $n=5000$ のとき
    • $\log_2 n \simeq 12.29$
    • 実際に大きさ1の配列になるまでに必要な分割数は以下の通り13回
      • → 2500 → 1250 → 625 → 313 → 157
      • → 79 → 40 → 20 → 10 → 5
      • → 3 → 2 → 1
    • 実際の計算回数と理論値の差は $(12.29-13)/13 = -5.46$ %
      • $n=4000$ のときに比べて誤差が大きい

$\log_2 n$ 切り上げによるずれの大きさは $n$ の値によって異なるため、最小二乗法による回帰結果に対して波打つような誤差が生じるのではないか？