Pythonでマージソートを実装する方法をわかりやすく解説

マージソート（Merge Sort）は、代表的なソートアルゴリズムのひとつです。ソート対象の配列の長さを n とすると、計算量は O(n log n) となり、非常に効率的な並べ替え手法として知られています。

マージソートは「分割統治法（Divide and Conquer）」という考え方に基づいたアルゴリズムです。まず、配列を半分ずつに再帰的に分割していき、要素が1つになるまで分割を続けます。その後、要素が1つだけのリスト同士を順にマージ（併合）しながら整列させていき、最終的に完全にソートされたリストを作り上げます。

この一連の処理によって、整列済みの配列を得ることができます。

マージソートの仕組み

下図のように、マージソートの動作は「分割」と「マージ」の2つのフェーズで理解できます。

紫のボックスと黒い矢印：リストを2つに分割していく過程を示しています。

緑のボックスと赤い矢印：ソート済みの2つのリストをマージしていく過程を示しています。

Pythonでのマージソートの実装

リストを半分に分割する処理はシンプルで、要素が1つになるまで再帰的に繰り返します。その後に行うのがマージ処理で、ここがマージソートの核心となる部分です。2つのソート済みリストを1つの整列済みリストへと結合するロジックをここで実装します。

コード例

merge 関数は、マージ対象となる2つのソート済み配列を受け取ります。a1 の先頭要素と a2 の先頭要素を比較し、小さい方をリスト c に追加します。そして、追加した側の配列のポインタを1つ進めます。この操作を片方の配列が空になるまで繰り返し、残った要素をすべて c の末尾に追加すれば完成です。

def merge(a1, a2):
    c = []
    x = 0
    y = 0
    while(x < len(a1) and y < len(a2)):
        if(a1[x] < a2[y]):
            c.append(a1[x])
            x += 1
        else:
            c.append(a2[y])
            y += 1
    while(x < len(a1)):
        c.append(a1[x])
        x += 1
    while(y < len(a2)):
        c.append(a2[y])
        y += 1
    return c

def mergesort(array):
    if(len(array) == 1):
        return array
    mid = (len(array)) // 2
    a1 = mergesort(array[:mid])
    a2 = mergesort(array[mid:])
    return merge(a1, a2)

array = [2, 3, 1, 5, 4, 6, 8, 10, 7, 9]
print(mergesort(array))

実行結果

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

このように、マージソートは再帰的な分割とマージを組み合わせることで、安定かつ高速にデータを並べ替えることができます。大量のデータを扱う場面でも信頼性の高いアルゴリズムなので、ぜひ実際にコードを書いて動作を確認してみてください。