【Python】マージソート【アルゴリズム】

  • 2021年12月15日
  • 2022年8月1日
  • Python
  • 225View
  • 0件

はじめに

マージソートの Python サンプルコードを紹介します。

Wikipedia マージソート

サンプルコード

サンプルコードの紹介です。
merge_sort 関数を再帰的に呼び出すことで、まずは小さなリストから整列を行うようにしています。
そして整列されたリスト同士をマージすることでソートを実現しています。
これを分割統治法といいます。

なお、サンプルコードでは元のリストを破壊しません。

def merge_sort(xs):
    if len(xs) == 1:
        return xs
    mid = len(xs) // 2
    lhs = merge_sort(xs[:mid])
    rhs = merge_sort(xs[mid:])
    print(lhs, rhs)
    return merge(lhs, rhs)


def merge(lhs, rhs):
    ref_l = 0
    ref_r = 0
    merged = []

    while ref_l < len(lhs) and ref_r < len(rhs):
        if lhs[ref_l] < rhs[ref_r]:
            merged.append(lhs[ref_l])
            ref_l += 1
        else:
            merged.append(rhs[ref_r])
            ref_r += 1

    merged.extend(lhs[ref_l:])
    merged.extend(rhs[ref_r:])
    return merged


if __name__ == '__main__':
    xs = [8, 4, 3, 7, 6, 5, 2, 1]
    print('initial:', xs)
    xs = merge_sort(xs)
    print('sorted :', xs)

以下は出力例です。

❯ python3 merge_sort.py 
initial: [8, 4, 3, 7, 6, 5, 2, 1]
[8] [4]
[3] [7]
[4, 8] [3, 7]
[6] [5]
[2] [1]
[5, 6] [1, 2]
[3, 4, 7, 8] [1, 2, 5, 6]
sorted : [1, 2, 3, 4, 5, 6, 7, 8]

おしまい!