マージソート｜大きい順のソーティング

5781 ワード
Python3 ソートアルゴリズム マージソート Python3 テキストリンク

マージソートをPythonで

分割してまた結合（マージ）して

マージソートは、ソートする値が入ったリストを２つに分割することを繰り返し、バラバラにした後、今度は結合（マージ）するときに大きい順（小さい順もOK）に並べ替えていくソーティングアルゴリズムです。

・ソースコードは以下の通りです

mergeSort.py
data = [6,13,12,65,76,22,43,87,14,9]

def merge_Sort(data):
    if len(data) <= 1:
        return data

    mid = len(data) // 2 # ど真ん中のインデックス取得
    # 再帰的に分類
    left = merge_Sort(data[:mid]) # 左側を分割
    right = merge_Sort(data[mid:]) # 右側を分割
    # 結合（マージ）
    return merge(left, right)

def merge(left, right):
    result = []
    ii, jj = 0, 0

    while ( ii < len(left)) and (jj < len(right)):
        if left[ii] >= right[jj]:
            result.append(left[ii])
            ii += 1
        else:
            result.append(right[jj])
            jj += 1

    # 残りを一気に追加する
    if ii < len(left):
        result.extend(left[ii:]) # 左側残りを追加
    if jj< len(right):
        result.extend(right[:jj]) # 右側残りを追加
    return result

print(merge_Sort(data))

# 結果
# [87, 76, 65, 43, 22, 13, 12, 6]

特徴として、メモリに入りきらないような大容量のデータがあったとして、分割した別の箇所でそれぞれソーティングしておいて、それから結合しながらデータを作成することも可能となります。