マージソートとは？
ソートの一種。安定したソート。分割統治法（divide-and-conquer）を使用している。
- ソート対象の配列を２分割する（divide）
- 分割したものをさらに２分割するのを要素が１つになるまで繰り返す（divide）
- それぞれの先頭要素同士を比較して、小さい数値を前方にしてマージ(solve, merge)
- ソート済み同士の要素の最初の数値を比較して小さい方から並べてマージ(conquer, merge)
参考：鹿児島大学HP
マージソートのコード
#最少単位に分解後にmergeを行う。この処理を繰り返す
def merge_sort(arr):
#要素が1つか０のときはその配列をそのまま返す。（比較対象がなくソートの必要性がないため）
if len(arr) <= 1:
return arr
#２分割する。スライスで切り分けるため、整数部のみ抽出する
mid = len(arr)//2
#元の配列を２分割
arr1 = arr[:mid]
arr2 = arr[mid:]
#最少単位になるまで２分割を続ける
#returnになった時点で再帰が終了する
arr1 = merge_sort(arr1)
arr2 = merge_sort(arr2)
return merge1(arr1, arr2)
#２つの要素を比較して、小さい方を先頭に並べる
def merge1(arr1,arr2):
#マージ結果を入れる配列
merged = []
l_i, r_i =0,0
while l_i < len(arr1) and r_i < len(arr2):
if arr1[l_i] <= arr2[r_i]:
merged.append(arr1[l_i])
l_i += 1
else:
merged.append(arr2[r_i])
r_i += 1
if l_i < len(arr1):
merged.extend(arr1[l_i:])
if r_i < len(arr2):
merged.extend(arr2[r_i:])
return merged
確認
list=[7,4,3,5,6,1,2]
merge_sort(list)
#[1, 2, 3, 4, 5, 6, 7]
マージソートの詳細
２つの関数が走っているためわかりにくいので分解してみる。
- 最少単位を作る関数(div_arr)
- 比較して小さい方を配列に追加していく関数(merge)
最少単位を作る関数
まずは、各要素を全て分割する関数を考える
def div_arr(arr):
#要素が1つか０のときはその配列をそのまま返す。（比較対象がなくソートの必要性がないため）
if len(arr) <= 1:
return print(arr)
#２分割する。スライスで切り分けるため、整数部のみ抽出する
mid = len(arr)//2
#元の配列を２分割
arr1 = arr[:mid]
arr2 = arr[mid:]
#最少単位になるまで２分割を続ける
#returnになった時点で再帰が終了する
arr1 = div_arr(arr1)
arr2 = div_arr(arr2)
確認
list=[7,4,3,5,6,1,2]
div_arr(list)
[7]
[4]
[3]
[5]
[6]
[1]
[2]
ポイントはarr1とarr2の2つを用意していること。
関数に投入された値は２分割され、後方（arr2）は常に処理がストックされる。
このため、arr1がreturnで終了したあとも、arr2がストックされた分だけ処理され続ける。
return arrで配列が出力されることを想定していたが、何も表示されたないため、return print(arr)にしている。（なぜ表示されないか不明、、）
（参考）前列だけで再帰処理した場合
def div_arr(arr):
if len(arr) <= 1:
return print(arr)
mid = len(arr)//2
arr1 = arr[:mid]
arr1 = div_arr(arr1)
list=[7,4,3,5,6,1,2]
div_arr(list)
[7]
arr1しか処理しないため、[7]だけが出力される。
※[7],[4],[3]とならない。再帰処理を繰り返す中で、[4],[3]はarr2に割り振られるため。
比較して小さい方を配列に追加していく関数
#２つの要素を比較して、小さい方を先頭に並べる
def merge1(arr1,arr2):
#マージ結果を入れる配列
#初期値0だが、mergeを繰り返す度に中身が増えていく
merged = []
#対比する要素の配列番号初期値
l_i, r_i =0,0
#ループ終了条件。どちらかの配列を全て比較仕切ったら終了
while l_i < len(arr1) and r_i < len(arr2):
#前方の要素の方が小さい場合
#同じ場合は先方を優先するためイコールをつける
if arr1[l_i] <= arr2[r_i]:
merged.append(arr1[l_i])
#同じ要素を再度検証しないよう配列番号に１をたす。
l_i += 1
else:
merged.append(arr2[r_i])
r_i += 1
# while文が終了したら、追加されていない方を丸ごと答えに追加する。
# 各配列は既に昇順にソート済みであるため、そのまま追加している。
if l_i < len(arr1):
merged.extend(arr1[l_i:])
if r_i < len(arr2):
merged.extend(arr2[r_i:])
return merged
確認
a=[2,3]
b=[1,8,9]
merge1(a,b)
#[1, 2, 3, 8, 9]
全体の処理の流れを可視化
上記２つの処理を踏まえて、merge_sortの処理を見てみる。
#ソートする配列
arr=[7,4,3,5,6]
#1回目の処理
arr1=[7,4]
arr2=[3,5,6]
#arr1を再帰
arr1`=[7]
arr2`=[4]
##arr1の解##
merge`=[4,7]
#arr2を再帰
arr1``=[3]
arr2``=[5,6]
#arr2``を再帰
arr1```=[5]
arr2```=[6]
##arr2``の解##
merge``=[5,6]
##arr2の解##
merge```=[3,5,6]
##いよいよarrの解##
merge=[3,4,5,6,7]
##arrの解はarr1とarr2をmergeしたもの
#arr1の解 merge`=[4,7]
#arr2の解 merge```=[3,5,6]
、、ややこしい。最後の3行が肝心
arr1 = merge_sort(arr1)
arr2 = merge_sort(arr2)
return merge1(arr1, arr2)
merge_sortの度にmergedした値（merge1の結果）がarr1とarr2に入る。
それがさらにmergeされていく。
これで最少単位まで分解した要素が再度組み上がる。
これ考えた人すげぇ、、そしてこれを理解している人もすげぇ