Pythonでマージソートを実装する方法を徹底解説!サンプルコード付き

この記事では、マージソート(Merge Sort)のアルゴリズムを使って配列を並べ替えるPythonプログラムについて、実際のコード例を交えながら詳しく解説します。

問題設定

課題 − 与えられた配列を、マージソートの考え方を用いて昇順に並べ替えます。

マージソートは分割統治法に基づく整列アルゴリズムです。まず配列を半分ずつ再帰的に分割し、要素が1つになった時点でそれを「ソート済み」とみなします。その後、隣り合う部分配列同士を先頭から比較しながら統合(マージ)していくことで、最終的に配列全体が整列されます。

Pythonでの実装例

# マージ関数
def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    # 一時配列を作成
    L = [0] * (n1)
    R = [0] * (n2)
    # データを一時配列へコピー
    for i in range(0, n1):
        L[i] = arr[l + i]
    for j in range(0, n2):
        R[j] = arr[m + 1 + j]
    i = 0  # 前半部分のインデックス
    j = 0  # 後半部分のインデックス
    k = l  # 統合後の書き込み位置
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
    # 左半分に残った要素をコピー
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
    # 右半分に残った要素をコピー
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

# ソート本体
def mergeSort(arr, l, r):
    if l < r:
        # 中央位置を計算
        m = (l + r) // 2
        # 再帰的に分割してソート
        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, m, r)

# メイン処理
arr = [2, 5, 3, 8, 6, 5, 4, 7]
n = len(arr)
mergeSort(arr, 0, n - 1)
print("Sorted array is")
for i in range(n):
    print(arr[i], end=" ")

実行結果

Sorted array is
2 3 4 5 5 6 7 8

プログラムのポイント

merge関数の役割

merge関数は、左半分(L)と右半分(R)という2つのソート済み部分配列を受け取り、それらを1つの整列済み配列に統合します。L[i]とR[j]の値を比較し、小さい方から元の配列arrへ順番に書き戻していきます。どちらか一方を使い切った後は、残りの要素をそのままコピーすれば完了です。

mergeSort関数の役割

mergeSort関数は再帰的に呼び出され、配列の中央位置mを求めて左右に分割します。範囲が1要素以下になると再帰が止まり、呼び出し元へ戻る過程でmerge関数によって順次統合されていきます。

なお、中央位置の計算には(l + r) // 2を使用しています。Python 3では「/」は小数を含む除算(float)となるため、リストのインデックスとして使うには整数除算の「//」を使う必要があります。

変数のスコープ

このプログラムで使われるすべての変数はローカルスコープで宣言されています。各関数内で定義された変数(L、R、i、j、kなど)は、関数の外部からは参照できない点に注意してください。

マージソートの計算量

マージソートの計算量は、入力データの初期状態に関わらず常にO(n log n)です。また、同じ値の相対的な順序が保たれる「安定なソート」である点も大きな特徴です。一方で、統合時に一時配列が必要となるため、追加のメモリ領域としてO(n)を必要とします。

まとめ

この記事では、Pythonでマージソートを実装する方法を学びました。「分割して統合する」というシンプルな発想でありながら、常に高速かつ安定した性能を発揮できるのがマージソートの魅力です。ぜひ実際にコードを動かして、挙動を確認してみてください。