はじめに
マージソートの Python サンプルコードを紹介します。
サンプルコード
サンプルコードの紹介です。
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]おしまい！