Pythonでソートアルゴリズムの再発明をしてみる: マージソート

概要

• Pythonでソートアルゴリズムを再発明してみるだけ
• 今回はマージソートについて
• 参考サイトのサンプルコードをできるだけ見ずに実装する
• とりあえず昇順ソートのみの対応とする

マージソートの概要

• どのような条件でもわりと安定して速い
• 安定ソート

基本的な手順

1. リストを半分に分割する（要素の大きさに関係なく、単純に分割する）
2. 手順1について、要素数が全て1つになるまで繰り返す
3. ソート済みのリスト同士をマージする。先頭要素を比較し、小さい方から順に別のリストに詰めていく（※要素数が1のリストも「ソート済み」とみなせる）
4. 手順3を繰り返し、分割したリストが全てマージされたらソート完了

ソース

import random

def merge_sort(lst):
    # 再帰の終了条件
    if len(lst) == 0 or len(lst) == 1:
        return lst

    # 分割
    # 今の実装だと要素数が奇数の場合は余りの要素が後ろに入るが、どちらでもよいはず
    length = len(lst)
    firstHalf = lst[0:length // 2]
    latterHalf = lst[length // 2:length]
    
    # 再帰呼び出し。戻り値はソートされた状態になっている
    firstHalf = merge_sort(firstHalf)
    latterHalf = merge_sort(latterHalf)

    # マージ処理。それぞれの先頭要素を見て小さいほうからresultに詰めていけば全体がソートされたリストになる
    result = []
    while True:
        a = firstHalf[0]
        b = latterHalf[0]
        
        # 小さいほうをresultに追加し、元のリストからは削除
        # ここが逆なら降順ソートになる
        if a < b:
            result.append(a)
            firstHalf.pop(0)
        else:
            result.append(b)
            latterHalf.pop(0)

        # 両方とも空なら完了
        if len(firstHalf) == 0 and len(latterHalf) == 0:
            break
        
        # 片方だけ空なら、空じゃないほうをresultの後ろに足す
        if len(firstHalf) == 0:
            result +=  latterHalf
            break

        if len(latterHalf) == 0:
            result +=  firstHalf
            break

    return result


lst = list(range(10))
random.shuffle(lst)

print("ソート前: " + str(lst))

lst = merge_sort(lst)

print("ソート後: " + str(lst))

参考サイト

• https://ja.wikipedia.org/wiki/マージソート