tetoblog 
本記事はPythonのマージソートについて、優しく解説しています。ソートとは数値や文字列を昇順や降順に並べ替えることで、プログラミングを学ぶ上で非常に重要な道具です。ソートの中でも極めて重要なマージソートを一緒に学習しましょう！
マージソートとは？
マージソートは、様々なソートアルゴリズムの中でも、非常に高速でよく利用されている整列アルゴリズムです。
クイックソートよりは殆どの場合で速度が劣るものの、マージソートとクイックソートは非常に高速でよく利用されています。
クイックソートについて曖昧な方は、下の記事で解説していますので、ぜひご覧ください。
クイックソートとは？【アルゴリズム紹介・Pythonによる実行】
「マージソート」は英語で書くと「merge sort」ととなり、ここで「merge」は「合わせる」や「併合する」という意味があります。マージソートではこの言葉のように、一度分割したそれぞれの要素順に合わせていくことでソートしています。
マージソートのアルゴリズムについて、
下の動画が、序盤は良い意味でふざけていますが非常に分かりやすく解説していますので、アルゴリズムの仕組みについてぜひご覧ください。
いかがでしたか。
マージソートについて、手順を３ステップでまとめました。
１．データの要素を２分割する
２．分割したデータを整列する
３．整列したデータをマージする
図で表すと下のような感じです。分割を行い、整列（マージ）を行います。
（１年半前に大学の課題で提出した図なので、字が汚なくてすみません（笑））
下の動画もマージソートについて、処理速度やアルゴリズムを非常によく理解する事ができます。
マージソートの計算量
| 平均計算時間 | 最悪計算時間 | 最良計算時間 |
| Ｏ（n*log(n)） | Ｏ（n*log(n)） | Ｏ（n*log(n)） |
マージソートの計算量は「Ｏ（n*log(n)）」です。また、マージソートは安定性のある整列アルゴリズムです。並列で処理が可能な点・処理速度が高速な点、がマージソートの大きな利点です。
マージソートの欠点
速度が安定していて早いものの、並べ替える要素数の数だけメモリが必要となるため、クイックソートよりかは速度が劣ります。
分割後にマージする際、別のソートアルゴリズムを利用することで更に処理速度を向上させることもできます。
Pythonコード
def merge_sort(nums):
if len(nums) <= 1:
return nums
#２分割
split = len(nums) // 2
left = nums[:split]
right = nums[split:]
#要素数が１になるまで繰り返し分割（再帰関数）
left = merge_sort(left)
right = merge_sort(right)
#マージ（併合）処理
i, j, k= 0, 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
nums[k] = left[i]
i += 1
else:
nums[k] = right[j]
j += 1
k += 1
while i < len(left):
nums[k] = left[i]
i += 1
k += 1
while j < len(right):
nums[k] = right[j]
j += 1
k += 1
return nums上記がPythonを用いて作成したバケットソートの関数です。
１１〜１２行目の再帰関数で、繰り返し分割を行い、
１５行目〜３５行目でマージを行っています。
マージソートの実行例
上記で作成した関数を使用して、実際にマージソートをPython環境で実行してみました。
下記がそのコードと実行結果です。
def merge_sort(nums):
if len(nums) <= 1:
return nums
split = len(nums) // 2
left = nums[:split]
right = nums[split:]
left = merge_sort(left)
right = merge_sort(right)
i, j, k= 0, 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
nums[k] = left[i]
i += 1
else:
nums[k] = right[j]
j += 1
k += 1
while i < len(left):
nums[k] = left[i]
i += 1
k += 1
while j < len(right):
nums[k] = right[j]
j += 1
k += 1
return nums
if __name__ == '__main__':
nums = [32, 4, 55, 99, 34, 21, 18]
print(merge_sort(nums))【実行結果】
[4, 18, 21, 32, 34, 55, 99]実行結果から、
３５行目で宣言した[32, 4, 55, 99, 34, 21, 18]のリストを昇順に上手くソートできていることがわかります。
ということで、本記事はマージソートについて、Pythonのコードを使用しながら紹介しました。
最後まで読んでいただき、ありがとうございました＼(^o^)／
超オススメのPC用品
PCを操作する上で、トラックボールマウスが非常におすすめです！
僕も感動したこのマウスを、騙されたと思って使ってみてください！(^^)
外部モニターで２倍以上の効率化が見込めます！
安いものだと、たったの１万円前後なのでおすすめですよー！＼(^o^)／
