マージソートとはソート（並び替え）アルゴリズムの一種で、与えられたリストに対して一定のルールのもとで並び替えるアルゴリズムです。
具体的な例で考えていきましょう
具体例
arrに数字の入ったリストを仮定してみます。
arr = [12, 11, 13, 5, 6, 7]
これをマージソートを使うことで、
[5, 6, 7, 11, 12, 13]
と小さい順に並び替えていきます。
どうやって並び替えるのか（アルゴリズム）
[12, 11, 13, 5, 6, 7]
↓ A
[12,11,13] [5,6,7]
↓ B, D
-------------------
[12,11] [13]
↓ C
[12][11]
-------------------
＆
-------------------
[5,6] [7]
↓ E
[5] [6]
-------------------
このようにリストを最後には一つの要素になるまで２分割していきます。
＊次の操作ですが、下から順番で目で追ってください
[ 5, 6, 7, 11, 12, 13]
↑
[11,12,13] [5,6,7]
↑ G I
-------------------
[11,12] [13]
↑ F
[12][11]
-------------------
＆
-------------------
[5,6] [7]
↑ H
[5] [6]
-------------------
リストの最初の値から大小を比べて小さい順に左側に配置いて元のリストと同じ長さのソートされたリストに戻します。(要素が１つになるまで分解してから、大小を比較してリストに戻っているので、全てのマージ済のリストは小さい順になっている)
実際のコード
def mergeSort(arr, l, r):
if l < r:
# ①真ん中のインデックスを設定
m = l+(r-l)//2
# ②リストを左右に順番で分割
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
# ③左右のリストをマージ(合併する)
merge(arr, l, m, r)
def merge(arr, l, m, r):
#準備編
n1 = m - l + 1
n2 = r - m
# 全ての要素が０の新しいリストを2つ作る。
L = [0] * (n1)
R = [0] * (n2)
# 上で作ったリストにarrのデータを前半と後半で分けて渡す
for i in range(0, n1):
L[i] = arr[l + i]
for j in range(0, n2):
R[j] = arr[m + 1 + j]
# 全てのリストの操作の数を数える変数をセットアップする
i, j, k = 0,0,l
# 大小比較編
# ここ以降で大小を比較して、小さい順になるように左右入れ替える
# LもRもまたリストが空でない状態の時
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Lのリストだけ空でない状態の時＝Rのリストが空の時
while i < n1:
arr[k] = L[i]
i += 1
k += 1
# Rのリストだけ空でない状態の時＝Lのリストが空の時
while j < n2:
arr[k] = R[j]
j += 1
k += 1
#実際にリストを与えて関数を実行
arr = [12, 11, 13, 5, 6, 7]
mergeSort(arr, 0, len(arr)-1)
print(arr)
プログラムの解説
マージソートは主に2つのパートに別れています。１、リストを左右に分割に分ける。２、左右のリストをマージ(合併)して新しいリストに左右のリストから小さい順でならび変えて行きます。
１、リストを左右に分割に分ける
１番の機能はmergeSort関数が該当します。
recursion(再帰)と呼ばれるアルゴリズムが使われておりややこしいので念入りに解説できればと思います。
もしrecursion(再帰)をご存知でない人がいらっしゃればこちらを先に見てみてください。
再帰は本当に何が起こっているかが分からないので、print()でその都度処理を可視化してあげると分かりやすいです。
なので、コードをこんな感じでmergeSort関数内にprint()文を入れてみました
def mergeSort(arr, l, r):
if l < r:
# ①真ん中のインデックスを設定
m = l+(r-l)//2
print("① Left", arr[l:m+1])
print("① Right",arr[m+1:r+1])
# ②リストを左右に順番で分割
mergeSort(arr, l, m)
print("②A Left",arr[l:m+1])
print("②A Right",arr[m+1:r+1])
mergeSort(arr, m+1, r)
print("②B Left",arr[l:m+1])
print("②B Right",arr[m+1:r+1])
# ③左右のリストをマージ(合併する)
merge(arr, l, m, r)
print("I am done")
これでどのprint()文が実行され、リストの変化を見ることができます。
全体の実行結果
① Left [12, 11, 13]
① Right [5, 6, 7]
① Left [12, 11]
① Right [13]
① Left [12]
① Right [11]
②A Left [12]
②A Right [11]
②B Left [12]
②B Right [11]
I am done
②A Left [11, 12]
②A Right [13]
②B Left [11, 12]
②B Right [13]
I am done
②A Left [11, 12, 13]
②A Right [5, 6, 7]
① Left [5, 6]
① Right [7]
① Left [5]
① Right [6]
②A Left [5]
②A Right [6]
②B Left [5]
②B Right [6]
I am done
②A Left [5, 6]
②A Right [7]
②B Left [5, 6]
②B Right [7]
I am done
②B Left [11, 12, 13]
②B Right [5, 6, 7]
I am done
[5, 6, 7, 11, 12, 13]
I am doneで関数の全てが実行されている(merge関数が呼び出されているう)ことになるので、I am doneのメッセージで一旦分けて個別で解説したいと思います。
１つ目のブロック
① Left [12, 11, 13]
① Right [5, 6, 7]
① Left [12, 11]
① Right [13]
① Left [12]
① Right [11]
②A Left [12]
②A Right [11]
②B Left [12]
②B Right [11]
I am done
[12,11,13,5,6,7]の分解がされてます(A)
① Left [12, 11, 13]
① Right [5, 6, 7]
[12,11,13]の分解がされてます(B)
① Left [12, 11]
① Right [13]
[12,11]の分解がされてます(C)
① Left [12]
① Right [11]
[12],[11]と初めて要素が１つずつのリストになったので、１回目のmergeが行われてます。(F)
②A Left [12]
②A Right [11]
②B Left [12]
②B Right [11]
I am done
これにより[11,12]ができあがります。
2つ目のブロック
[11,12][13]のマージが行われてます(G)
②A Left [11, 12]
②A Right [13]
②B Left [11, 12]
②B Right [13]
I am done
これにより[11,12,13]ができあがります。
３つ目のブロック
②A Left [11, 12, 13]
②A Right [5, 6, 7]
① Left [5, 6]
① Right [7]
① Left [5]
① Right [6]
②A Left [5]
②A Right [6]
②B Left [5]
②B Right [6]
I am done
[5,6,7]の分解が行われてます(D)
① Left [5, 6]
① Right [7]
[5,6]の分解が行われてます(E)
① Left [5]
① Right [6]
[5],[6]が１つずつのリストになったので、3回目のmergeが行われてます。(H)
②A Left [5]
②A Right [6]
②B Left [5]
②B Right [6]
I am done
これにより[5,6]ができあがります。
４つ目のブロック
[5,6][7]のマージが行われてます(I)
②A Left [5, 6]
②A Right [7]
②B Left [5, 6]
②B Right [7]
I am done
これにより[5,6,7]ができあがります。
５つ目のブロック
[11,12,13][5,6,7]のマージが行われてます(J)
②B Left [11, 12, 13]
②B Right [5, 6, 7]
I am done
これにより[5, 6, 7, 11, 12, 13]が出来上がります。
２、左右のリストをマージ(合併)する
２番の内容はmerge関数が該当します。
merge関数は主に準備編、大小比較編に別れます。
準備編
準備編で定義(用意)している変数は以下になります。
n1, n2, L, R, i, j, k
n1とn2は左右のリストの要素の数を関数の引数を使って計算します。
LとRでは左右のリストを新たに作ります。
print([0]*(Int型の値))
を実行して貰えばわかりますが、[0,0, ..., 0]のような０要素が(Int型の値)個入ったリストができます。
i,j,kは何回左(i)、右(j)、arr[k]の操作を行ったかを記憶しておくためのものです。
大小比較編
LとRはそれぞれ小さい順に並び変えられた要素が入っています。
実質大小を比較しているのは3つのwhileのうち初めの「LもRもまたリストが空でない状態の時」の条件ついたwhile文です。
if L[i] <= R[j]:
この条件はi番目のL(左)のリストの要素がR(右)のリストの要素より小さいか等しいという意味です。左の方が小さいことになるので、左の要素をリストにいれます。(等しい場合はどっちを入れてもいいのでスルー)
else:
それ以外ということは、i番目のR(左)のリストの要素がL(左)のリストの要素より小さいという意味ので、右のリストの値を入れます
残りの2つのwhileはどちらかのリストが空になった時に使われます。
例えば、L=[2,3], R=[1,5] → L=[], R=[5], arr=[1,2,3]のような場合。
この例だと３番目のwhile以下の処理が実行されます。
参考文献
Python Program for Merge Sort - GeeksforGeeks
