【Python】再帰を使わない反復型（ボトムアップ）マージソートの実装方法を解説

この記事では、反復処理（イテレーション）のみでマージソートを実装する方法について解説します。再帰呼び出しを使わずに、whileループだけで配列を整列させる「ボトムアップ方式」のアプローチを見ていきましょう。

問題文

問題： 与えられた配列を、反復処理によるマージソートの考え方を用いて昇順に並べ替えてください。

例として、次の整数配列を扱います。

a = [2, 5, 3, 8, 6, 5, 4, 7]

反復マージソートの考え方

通常のマージソートは再帰を使って配列を分割しますが、反復版では最初から要素数1の部分配列として捉え、隣接する部分配列同士を統合（マージ）しながらサイズを倍々に増やしていくのが特徴です。

具体的な流れは以下のとおりです。

• まず、幅1の部分配列同士をマージして、幅2の整列済みブロックを作ります。
• 次に、幅2のブロック同士をマージして、幅4の整列済みブロックを作ります。
• この操作を、部分配列の幅が配列全体の長さに達するまで繰り返します。

すべての変数はローカルスコープで宣言されており、ループごとに left（左端）、mid（中央）、right(右端）のインデックスを計算し、その範囲に対してマージ処理を適用します。

実装例

# 反復方式のマージソート
def merge_sort(a):
    current_size = 1

    # 部分配列のサイズを倍増させながら走査
    while current_size < len(a):
        left = 0

        # 各ブロックをマージしていく
        while left < len(a) - 1:
            # 中央位置を計算（配列末尾を超えないよう制限）
            mid = min(left + current_size - 1, len(a) - 1)
            # 右端を計算（配列末尾を超えないよう制限）
            right = min(left + 2 * current_size - 1, len(a) - 1)

            # マージ処理を実行
            merge(a, left, mid, right)
            left += current_size * 2

        # 次のステップでは部分配列のサイズを2倍にする
        current_size *= 2


# マージ処理：2つの整列済み部分配列を1つに統合する
def merge(a, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    L = [0] * n1
    R = [0] * n2

    for i in range(n1):
        L[i] = a[l + i]
    for j in range(n2):
        R[j] = a[m + 1 + j]

    i, j, k = 0, 0, l

    # L と R を比較しながら小さい方を元の配列へ戻す
    while i < n1 and j < n2:
        if L[i] > R[j]:
            a[k] = R[j]
            j += 1
        else:
            a[k] = L[i]
            i += 1
        k += 1

    # L に残った要素をコピー
    while i < n1:
        a[k] = L[i]
        i += 1
        k += 1

    # R に残った要素をコピー
    while j < n2:
        a[k] = R[j]
        j += 1
        k += 1


# 動作確認用コード
a = [2, 5, 3, 8, 6, 5, 4, 7]
merge_sort(a)
print("ソート後の配列:")
for i in range(len(a)):
    print(a[i], end=" ")

出力

ソート後の配列:
2 3 4 5 5 6 7 8

計算量について

反復マージソートの計算量は、再帰版と同じく以下のとおりです。

• 時間計算量： O(n log n) ― データ量に関わらず安定した性能を発揮します。
• 空間計算量： O(n) ― マージ時に一時的な補助配列が必要です。

再帰を使わないため、スタックオーバーフローの心配がなく、大きなデータセットでも安全に動作するという実用上のメリットがあります。

まとめ

この記事では、Pythonで再帰呼び出しに頼らず、whileループによる反復処理だけでマージソートを実装する方法を学びました。部分配列のサイズを1から始めて倍々に拡大しながらマージを繰り返すことで、配列全体を効率よく整列できることを確認しました。