マージソート
コード
関数の定義
merge_sort.py
def merge(A,left,mid,right):
n1 = mid - left + 1
n2 = right - mid
L=[]
R=[]
for i in range(n1):
L.append(A[left + i])
for j in range(n2):
R.append(A[mid + 1 + j])
L.append(float('inf'))
R.append(float('inf'))
i = 0
j = 0
for k in range(left,right + 1):
if L[i] <= R[j]:
A[k] = L[i]
i += 1
else:
A[k] = R[j]
j += 1
return A
def merge_sort(A,left,right):
if left < right:
mid = (left + right)//2
merge_sort(A,left,mid)
merge_sort(A,mid + 1,right)
merge(A,left,mid,right)
return A
使い方
merge_sort_use.py
A=[2,6,3,8,5]
print(marge_sort(A,0,4))
説明
関数mergeについて
・役割は、配列中のある部分に注目し、その部分を2つに分けた時、それぞれがソート済みだった場合に2つの配列を合わせて1つのソートされた配列を作る。
・ソートしたい部分の左端のインデックスをleft、右端をrightとし、2つに分ける際の境目をmidとする。
・前半のleft~midまでをサイズn1の新しい配列Lとし、後半のmid+1~rightまでを新しい配列Rとする。
・LとRの末尾に番兵として∞なる値を置いておく。
・LとRの先頭から順々に大きさを比較していき、小さいほうを配列Aのソートしたかった部分の先頭から代入していく。
関数merge_sortについて
・役割は、mergeを再帰的に用いてある配列のソートしたい部分をソートする。（左端をleft、右端をrightとする。）
・再帰的にmergeを用いる際、停止するのは配列の大きさが1まで分割されたとき、すなわちleft>=rightとなるとき。（個人的にはright-left>=1の間は実行するとかの方が分かりやすかったです。）
・まず、ある配列を2つに分けるため、真ん中のインデックスmidを求める。
・その前半と後半それぞれでまたmerge_sortを用いる。
参考文献
この記事は以下の情報を参考にして執筆しました。