Python で merge ソート


死ぬほどわかりやすい。


2段階に分けられます。1つ目は、2つに分けてソートする段階。2つ目は、分けてソートしたリストを統合する段階。

import random


def merge_sort(lst):
    if len(lst) == 1:
        return
    
    #
    # 1. 分割
    #
    n = len(lst)
    lst1 = [lst.pop() for _ in range(n // 2)]  # *1
    lst2 = [lst.pop() for _ in range(n - n // 2)]
    merge_sort(lst1)
    merge_sort(lst2)
    
    #
    # 2. 統合
    #
    lst1.reverse()  # *2
    lst2.reverse()
    while lst1 and lst2:
        if lst1[-1] <= lst2[-1]:
            lst.append(lst1.pop())
        else:
            lst.append(lst2.pop())
    
    while lst1:
        lst.append(lst1.pop())
    
    while lst2:
        lst.append(lst2.pop())


lst = list(range(100))
random.shuffle(lst)
merge_sort(lst)
print(lst)
print(len(lst))

1. 基本 pop メソッドで

メモリ消費量を抑えるため。最悪空間計算量 O(n) に準じるため。リスト内包表記を使えば、もっと綺麗に書けるけど...

lst1 = lst[len(lst) // 2]
lst1 = [lst.pop() for _ in range(n // 2)]

2. insert(0, value) はしないため

死ぬほど遅いから
Python で list を条件をつけて複数の要素を削除したい。