https://engineeringnote.hateblo.jp/entry/python/algorithm-and-data-structures/merge

本記事は、ソフトバンクパブリッシングから発行されている「」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、配列によるマージソート（Merge Sort）について学んでいきます。

マージソートとは

マージソート（Merge Sort）は、前回学んだクイックソートと同じ $O(n \log n)$ の計算量を誇る速いアルゴリズムですが、定数係数が大きいためクイックソートよりは遅いアルゴリズムになります。

マージソートでも、クイックソートで用いた分割統治（Divide and Rule or Divide and Conquer）というアプローチ方法で部分的に分けてから、マージ（併合）して整列を行います。

以下がマージソートを行う過程を簡略化したものになります。

マージソートでは、配列を $\frac{1}{2}$ ずつ分割していき、シーケンシャルに要素へアクセスしていきます。

そして、最終的に一つの要素になるまで再帰呼び出しをし、要素を分割できないまで進んだら、要素をマージしながら整列をさせていきます。

またマージソートには配列によるものと連結リストによるものがあり、今回は配列によるものを作成します。

配列によるものでは、マージした結果を保存するために別途入力データと同じサイズの配列を用意しなければならないため、その分記憶領域が必要となります。

この作業用の領域を確保しない方法もあるようですが、その分 $O(n)$ の計算量が別途必要になってきます。

なお、マージソートは安定な整列アルゴリズム（データの位置関係が保存される）になります。

Pythonでマージソートを実装してみる

それでは、Pythonでマージソートを実装してみます。

# merge_sort.py
import time
import pickle

def merge_sort(lst, low, high):
    if low >= high:
        return
    mid = int((low+high)/2)
    merge_sort(lst, low, mid)
    merge_sort(lst, mid+1, high)
    for i in range(low, mid+1):
        tmp_array[i] = lst[i]
    j = high
    for i in range(mid+1, high+1):
        tmp_array[i] = lst[j]
        j -= 1
    i = low
    j = high
    for k in range(low, high+1):
        if tmp_array[i] <= tmp_array[j]:
            lst[k] = tmp_array[i]
            i += 1
        else:
            lst[k] = tmp_array[j]
            j -= 1
            
with open('sample_data.pkl', 'rb') as f:
    lst = pickle.load(f)

MAX_ELEMENTS = len(lst)
tmp_array = [None for _ in range(MAX_ELEMENTS)]

start = time.time()
merge_sort(lst, 0, len(lst)-1)
print("elapsed {} sec".format(time.time() - start))