マージソート

「マージソート」は、「挿入ソート」より高速で、探索においては、現時点では最先端のアルゴリズムである。

マージソートは、分割統治アルゴリズムの一種である。
１）ソートされていない大きなリストから始める。リストをより小さなかたまりに繰り返し分割していく（分割）。この分割は、要素が1個のソート（統治）されたリストになるまで繰り返される（分割部分）。
２）分割したリスト（ソートされたリスト）をマージする。（マージ部分）
３）繰り返し、最終的に1つのソートされた大きなリストになるまで、このマージを繰り返す（ソート部分）。

マージ部分をキャビネットとファイルの例で考える。
2つのファイリングキャビネット（以下、オリジナルキャビネットと呼ぶ、それぞれ、左のキャビネット、右のキャビネットと呼ぶ。）があるとする。それぞれは個別に昇順にソートされているものとする。この2つの中身を1つの最終的なファイリングキャビネットにまとめて、完全にソートするには、下記のようにする。
１）2つのオリジナルキャビネットのそれぞれ先頭のファイルを比較する。左Tのキャビネットの最初のファイルの番号と右のキャビネットの最初の番号を比較し、番号の小さい方のファイルを、新しいキャビネットに最初のファイルとして挿入する。
２）左と右の先頭のファイルを比較し、番号の小さいほうを新しいキャビネットの最後に挿入する。
３）左右どちらかのキャビネットが空になったら、空ではないほうのキャビネットから残りのファイルをすべて取り出し、それらを新しいキャビネットの最後にまとめて入れる。

Pythonによるプログラム例：

#マージソートプログラム
import math

def merging(left,right): #マージタスク
newcabinet= []
while(min(len(left),len(right)) > 0):
if left[0] > right[0]:
to_insert = right.pop(0)
newcabinet.append(to_insert)
elif left[0] <= right[0]:
to_insert = left.pop(0)
newcabinet.append(to_insert)
if(len(left) > 0):
for i in left:
newcabinet.append(i)
if(len(right) > 0):
for i in right:
newcabinet.append(i)
return(newcabinet)

def mergesort(cabinet): #ソートタスク（含む分割）
newcabinet =[]
if(len(cabinet) == 1):
newcabinet = cabinet
else:
left = mergesort(cabinet[:math.floor(len(cabinet)/2)])  #再帰処理（分割）
right = mergesort(cabinet[math.floor(len(cabinet)/2):])  #再帰処理（分割）
newcabinet = merging(left,right)
return(newcabinet)

cabinet = list(map(int, input(“ソートしたい数字列を半角でスペースで区切って記載してください　”).split()))
# 4 1 3 2 6 3 18 2 9 7 3 1 2 5 -9 ← 入力例
sortedcabinet = mergesort(cabinet) #挿入ソート実施
print(“ソートした数字列　”,sortedcabinet) #結果出力

参考とした書籍
署名：アルゴリズムをめぐる冒険–勇敢な初学者のためのPythonアドベンチャー
著者：Bradford Tuckfield
訳者：竹川文則、川上悦子、高柳愼一
発行所：共立出版(株)

以上