Python で merge ソート

死ぬほどわかりやすい。

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

# 対話モード >>> に
# コピペで実行できます。
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. 分割
    #
    left = lst[:n // 2]  # *1
    right = lst[n // 2:]
    lst.clear()
    merge_sort(left)
    merge_sort(right)
    
    #
    # 2. 統合
    #
    left.reverse()  # *2
    right.reverse()
    while left and right:
        if left[-1] <= right[-1]:
            lst.append(left.pop())
        else:
            lst.append(right.pop())
    
    while left:
        lst.append(left.pop())
    
    while right:
        lst.append(right.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 を条件をつけて複数の要素を削除したい。