エンジニア実践的基礎: マージソート

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

マージソートとは

挿入ソートに引き続き、マージソートを学習します。マージソートは「バラバラにして並び替えて合体する」アルゴリズムです。これだけでは意味がわからないと思うので、カードの手札で例えます。

あなたは ３・２・４・１・6 の数が書かれたカードを持っています。まず最初にカードを間隔を開けて、それぞれのカードを横一列に並べます。この状態ではそれぞれのカードは独立しています。次に小さなグループで比較します。

最初は ３・２の二つのカードです。３は２より大きいので、二つのカードを入れ替えて ２・３とします。これらのカードは一つのグループとします。次の、このグループと４を比較します。つまり ２・３・４です。これはすでに大きい順なので、位置を入れ替える必要はありません。これも別のグループとします。次に、残りの １・６でグループにします。これも大きい順なので入れ替え不要です。ここまでで二つのグループが残っています：２・３・４と１・６です。二つのグループを左から順に比較して別の最終グループにします。２・１は１の方が小さいので、１が最初に最終グループに入ります。次に ２・６を比較します。２の方が小さいので２を最終グループに追加します。同じ手順で４・６は４が小さいので４を最終グループに追加します。最後に６が残ったので６を最終グループに追加して終わりです。カードは１・２・３・４・６と小さい順に並びました！

分割してソートして統合(マージ)するので、マージソートと呼ばれます。以下イメージです。

実装

若干トリッキーなのは再帰を利用している点です。再帰の回でお話ししたように、再帰は同じ構造で同じ処理を繰り返す処理に適しています。マージソートは分割・ソート・マージをグループに対して繰り返すので再帰処理で実装できます。最初は混乱するかもしれませんが、簡単なスケッチを書きながら処理を追えば理解できるはずです。

再帰を利用した実装
def mergeSort(arr, s, e):
    if e - s + 1 <= 1:
        return arr

    # 分割点(中央)のインデックスを計算
    m = (s + e) // 2

    # 分割点より左側のグループを再帰処理
    mergeSort(arr, s, m)

    # 分割点より右側のグループを再帰処理
    mergeSort(arr, m + 1, e)

    # ソートされた左グループと右グループをマージ
    merge(arr, s, m, e)
    
    return arr

def merge(arr, s, m, e):
    # 左右のグループを配列に分割
    L = arr[s: m + 1]
    R = arr[m + 1: e + 1]

    i = 0 # index for L
    j = 0 # index for R
    k = s # index for arr

    # 左右のグループから小さい順に値を並び替える
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # どちらかのグループに値が残る
    # 既にソートされてるので残りを全て新しいグループに追加する
    while i < len(L):
        arr[k] = L[i]
        i += 1
        k += 1
    while j < len(R):
        arr[k] = R[j]
        j += 1
        k += 1

計算量

空間計算量は O(n) です。データを２分割しながら再帰処理を繰り返すので、O(log n) のコールスタックが必要です。マージされたデータを維持するのに O(n) のメモリが必要です。O(n) は O(log n) より支配的なので、空間計算量は O(n) になります。

O(log n) はもう少し説明が必要かもしれないです。数学の話で恐縮ですが、底を2とした log は入力データ数を２分割し続けると何層分になるかを表します。例えば、８個のデータの場合、2^3 = 8 なので、log 8 = 3 です。これは3回2分割できることをあらわします。そのため3層分できます。

このイメージでは5個のデータを分割して３層分できる

コールスタックは呼び出し元のデータを記憶する場所で、再帰処理で後戻りする際に参照します。ちょうど習ったスタックと同じ原理です。スタックは最後に追加したデータをすぐに参照できましたね。層の数だけ呼び出し元が必要になるので、O(log n) のコールスタックを消費します。

時間計算量は O(n log n) です。これは層ごとに最悪ケースで n 回のソートが必要になるからです。

まとめ

マージソートは「バラバラにして並び替えて合体する」です。これを分割統治とも呼びます。このテクニックは今後いろいろな場面で出てくるので覚えておいてください。