アルゴリズムのモヤモヤをPythonで解消(5): マージソート

---
##### [前回] [アルゴリズムのモヤモヤをPythonで解消(4): 選択ソート](https://qiita.com/mingchun_zhao/items/d475e545252591d9f123)

## はじめに

`Pythonでアルゴリズムを楽しむ`、第5弾です。

## 今回のアルゴリズム: マージソート

### 問題

以下8つの数字を昇順で整列せよ。
`8	4	3	7	6	5	2	1`

### 解決案

マージソートを使用し、解決します。

- Wikipediaから[マージソート(merge sort)](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88)
    - ボトムアップの分割統治法による、ソートアルゴリズム
        - 大きい列を多数の列に分割し、それぞれマージする
            - 作業を並列化できる
        - 整列済み複数個の列を1個の列にマージする際
            - 小さいものから先に新しい列に並べることで、新しい列も整列される
    - 最悪計算時間: O($n\ log\ {n}$)
    - 最悪空間計算量: O(n)
        - in-placeのバリエーションも提案されている
            - in-placeは、入力の記憶領域を出力にも使うので、追加の作業記憶領域を必要としない
    - 安定ソートを実装可能
        - 分割と統合の実装に依存
    - クイックソートとの比較
        - クイックソートより、最悪計算時間は少ない
        - ただし、ランダムなデータでは、通常クイックソートが速い

- マージソートの手順
    - 1\. データ列を分割(通常、二等分)
    - 2\. 分割された各データ列で
        - 含まれるデータが1個の場合、それを返却
        - 2個以上なら、ステップ1から3を再帰的に適用しマージソート
    - 3\. 二つのソートされたデータ列(1個であればそれ自身)をマージ

- マージソートの動作例

|データ|処理内容|
|--|--|
|8 4 3 7 6 5 2 1|初期データ|
|8 4 3 7 \| 6 5 2 1|データ列を二分割|
|8 4 \| 3 7 \| 6 5 \| 2 1|再度二分割|
|4 8 \| 3 7 \| 5 6 \| 1 2|各データ列のデータ数が2以下となった<br>各データ列内のデータをソート|
|3 4 7 8 \| 1 2 5 6|右2つのデータ列、左2つのデータ列を<br>それぞれマージ/ソートし<br>2つのデータ列にする|
|1 2 3 4 5 6 7 8|2つのデータ列をマージ/ソートし<br>アルゴリズム終了|

- マージソート計算量
    - 最悪計算時間: O($n\ log\ {n}$)
    - 最良計算時間
        - 通常: O($n\ log\ {n}$)
        - `Natural Variant`: O(n)
    - 平均計算時間: O($n\ log\ {n}$)

### コード

```merge_sort.py
import matplotlib.pyplot as plt
import matplotlib.animation as ani
import matplotlib.cm as cm

def merge(arr, min, mid, max):
    new_arr = []
    i = min
    j = mid + 1
    while i <= mid and j <= max:
        if arr[i] < arr[j]:
            new_arr.append(arr[i])
            i += 1
        else:
            new_arr.append(arr[j])
            j += 1
    if i > mid:
        while j <= max:
            new_arr.append(arr[j])
            j += 1
    else:
        while i <= mid:
            new_arr.append(arr[i])
            i += 1
    for i, val in enumerate(new_arr):
        arr[min + i] = val
        yield arr

def merge_sort(arr, min, max):
    if max <= min:
        return
    elif min < max:
        yield arr
        mid = (min + max) // 2
        yield from merge_sort(arr, min, mid)
        yield from merge_sort(arr, mid + 1, max)
        yield from merge(arr, min, mid, max)
        yield arr

def plot(arr, rec, epochs):
    for rec, val in zip(rec, arr):
        rec.set_height(val)
        rec.set_color(cm.tab20(val % 15))
    text.set_text("count: {}".format(epochs[0]))
    epochs[0] += 1

if __name__ == '__main__':
    title = "merge sort"
    arr = [8, 4, 3, 7, 6, 5, 2, 1]
    nums = len(arr)
    algo = merge_sort(arr, 0, nums - 1)
    fig, ax = plt.subplots()
    ax.set_title(title)
    bar = ax.bar(range(len(arr)), arr, align='edge')
    ax.set_xlim(0, nums)
    ax.set_ylim(0, int(nums * 1.1))
    text = ax.text(0.01, 0.9, "", transform=ax.transAxes)
    epochs = [0]
    anim = ani.FuncAnimation(fig, func=plot, fargs=(bar, epochs), frames=algo, interval=500, repeat=False)
    mng = plt.get_current_fig_manager()
    mng.full_screen_toggle()
    plt.show()
```

- matplotlibがインストールされていない場合
```
$ pip install matplotlib
```
- 実行
```
$ python merge_sort.py
```
- 結果
    - ソート過程が可視化されます

![merge_sort.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2523098/52a8b803-1e67-58a9-a3c8-cafc8640c222.gif)

## おわりに

Pythonで`マージソート`アルゴリズムを解いてみました。
次回も続きます。お楽しみに。

##### [次回] [アルゴリズムのモヤモヤをPythonで解消(6): ヒープソート](https://qiita.com/mingchun_zhao/items/02de18a595042ce83525)