pythonでマージソートを実装してみた

今回はソートアルゴリズムの中でも今まで学んできたものよりも高速なアルゴリズムであるマージソートに関してpythonで実装していきたいと思います．
マージソートは基本的なソートアルゴリズムと比べると少し実装しづらい部分はありますが，全体の流れを掴むことと再帰関数をしっかりと使いこなすことができればそれほど苦戦せずに実装できると思います．

目次

マージソートとは

マージソートは配列全体に対して次の処理を行うようなソートを指します．

1. 指定されたn個の要素を含む部分配列をそれぞれn/2個の要素を含む2つの部分配列に分割する.

   1.1 部分配列は一つの要素になるまで分割を続ける

2. 2つの部分配列をそれぞれ順番通りに並ぶようマージ(合併)する

   2.1 部分配列がなくなるまで繰り返す

これらの流れを下図で確認してください.

図で流れを抑えると処理の行い方がより明確に伝わったと思います．
マージソートの土台は配列全体の1/2の大きさの部分配列を作りだすことと部分配列を統合していくことで作ることができます．

また，この分割フェーズに関しては1/2にしていくことを繰り返す，つまり，log₂n回の分割を行います．
一方でこの統合フェーズに関してはソート済みの配列を統合していきます．
つまり，必ずどちらかの配列の先頭要素のうち一つが統合後の配列の先頭要素になります．同様に統合後の二番目の配列要素に関してもどちらかの部分配列の要素にあり，この処理を繰り返していくことで統合することができます．よって，各階層でかかる計算量は常にO(n)となります．
これらのことよりマージソートはこれまで書いてきたソートアルゴリズムよりも早いO(nlogn)のアルゴリズムとなります．

マージソートの実装例

マージソートに関しての問題はALDS1_5_B:Merge Sortです．
マージソートの擬似コードなどが載っているので流れを確認したい方は見に行ってみてください.
では，早速実装していきたいと思います．

# mergesort
import random

#統合部
def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    for i in range(left,right):
        if len(L) == 0:
            A[i] = R.pop(0)
        elif len(R) == 0:
            A[i] = L.pop(0)
        elif L[0] <= R[0]:
            A[i] = L.pop(0)
        else:
            A[i] = R.pop(0)

#分割部
def mergesort(A, left, right):
    if left + 1 < right:
        mid = (left + right)//2
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)
        print(A)
            
    
A = [ i+1 for i in range(10)]
random.shuffle(A)
print(A)
mergesort(A,0,len(A))
print(A)

出力例

[8, 9, 3, 7, 10, 4, 6, 5, 1, 2]
[8, 9, 3, 7, 10, 4, 6, 5, 1, 2]
[8, 9, 3, 7, 10, 4, 6, 5, 1, 2]
[8, 9, 3, 7, 10, 4, 6, 5, 1, 2]
[3, 7, 8, 9, 10, 4, 6, 5, 1, 2]
[3, 7, 8, 9, 10, 4, 6, 5, 1, 2]
[3, 7, 8, 9, 10, 4, 6, 5, 1, 2]
[3, 7, 8, 9, 10, 4, 6, 1, 2, 5]
[3, 7, 8, 9, 10, 1, 2, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

コードの解説

mergesortの関数の部分では部分配列の位置を表すleftとright，また，その中央部分(分割部分)を表すmidをright - leftが2になるまで再帰的に呼び出しています．つまり，leftとrightに含まれる要素がそれぞれ一つになるまで呼び出しを続けています．
その後，再帰関数の呼び出しの逆順に統合部分の関数に値が投げられます．
統合部ではleftの位置にある配列Aの要素群とrightの位置にある配列Aの要素群の値の大小を群の先頭から順に比較しています．
一連の処理を終えると出力例の最終行のようにソートされた値が並ぶと思います．