Python で merge ソート


死ぬほどわかりやすい。


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

# 対話モード >>> に
# コピペで実行できます。
import random


def main():
    lst = list(range(100))
    
    # ランダム
    random.shuffle(lst)
    print(lst)
    
    # ソート
    merge_sort(lst)
    print(lst)


def merge_sort(lst):
    n = len(lst)
    if n == 1:
        return
    
    #
    # 1. 分割
    #
    lst1 = lst[:n // 2]  # *1
    lst2 = lst[n // 2:]
    lst.clear()
    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())


if __name__ == '__main__':
    main()

1. 基本 pop メソッドで

メモリ消費量を抑えるためにリスト内包表記を使うべきかな...

    # ここの箇所
    lst1 = lst[:n // 2]
    lst2 = lst[n // 2:]
    lst.clear()
    # リスト内包表記で書くべきか...
    lst1 = [lst.pop() for _ in range(n // 2)]
    lst2 = [lst.pop() for _ in range(n - n // 2)]


上の書き方だと新しいリストを作ってしまっている。 その分だけメモリを消費している。 マージソートの最悪空間計算量 O(n) に準じてるのかな.., そのあたりがちょっとわからない。

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

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