意外と面白い「ソートアルゴリズム」第三回：マージソート

2025/05/06

はじめに

こんにちは。デジタルステーション習志野スタッフの荒井です。

今回の記事では、大量の数字の列などを並び替えるときに使う「ソートアルゴリズム」について、今回は、効率的な手法の一つである、「マージソート」について解説していきます。

ちなみに、Eテレでは、「しめじソート」として紹介されていたりします。そっちのほうが聞きなじみがあるという方もいるかもしれません。

ソートアルゴリズムとは

まず、ソートアルゴリズムとは何か、簡単に説明します。

前提として、アルゴリズムとは、問題を解決するための手順や方法のことを言います。

そして、ソートアルゴリズムとは、大量のデータを、小さい順（昇順）や、大きい順（降順）など特定の並びに整列させるために考え出されたアルゴリズムのことを言います。

PCの処理では、エクスプローラーでのフォルダ管理や、表計算ソフトでの並び替えなど、何かしらのデータを並び替えることが多いです。

そのため、より早く、より少ない試行回数で目的を達成するため、今までに様々な手法が開発されています。

マージソートとは

マージソートは、ソートアルゴリズムの一種で、「分割統治法」という考え方を使って作られたソートアルゴリズムです。

手法としては、

1.分割

ソートしたいデータの配列を、半分に分割します。これを、要素が1つだけになるまで繰り返します。

2.結合

リストを結合していきます。

2つのリストの中身を比較して、リスト内で最も小さいもの同士を比較します。

その結果、小さかった方を別のリストに移し替えます。

これを繰り返し、結合していきます。

最終的にリストが1つにまとまったら、完成です。

マージソートの特徴としては、

最悪の場合の計算量が少ない
安定して動作する
追加のメモリ容量が必要
分割統治法や再起処理を使用しており、効率的

等があります。メモリ容量に余裕がある一般的なPCであれば、バブルソートやシェーカーソートよりも効率的にタスクをこなすことが出来ます。

実際にやってみる

正直、バブルソートなどに比べて複雑なので、言葉だけでは説明しづらい部分もあります。

では、実際にPythonを使って、マージソートをやってみましょう。

今回のマージソートに関しては、今まで紹介したソートアルゴリズムのように、リストを都度入れ替えるものではありません。

そのため、matplotlibを使ったグラフで表現するのがかなり難しいです。（グラフ描画用のコードでごちゃごちゃになります。）

なので今回は、以下にグラフなしサンプルコードと、参考程度に動画を載せる形とします。

import random

# マージソート

def merge_sort(data):

if len(data) <= 1:

return data

# リストを2つに分割する

mid = len(data) // 2

# 再起処理

left = merge_sort(data[:mid])

right = merge_sort(data[mid:])

# 2つのリストを合成する

result = merge(left, right)

return result

# リストを合成する処理

def merge(left, right):

# カウント用変数、集約用リスト

l,r=0,0

result = []

# 合成処理

while l<len(left) and r<len(right):

if(left[l] <= right[r]):

result.append(left[l])

l += 1

else:

result.append(right[r])

r += 1

# 余った方のリストを追加

if l < r:

result.extend(left[l:])

else:

result.extend(right[r:])

return result

data = random.sample(range(1,100), 50)

sorted = merge_sort(data)

print("instial array:", *data)

print("merge sorted:", *sorted)

出力結果は、以下のようになります。

instial array: 56 59 94 65 46 10 47 31 43 82 11 15 21 55 14 54 92 71 33 69 40 64 80 57 45 12 70 84 95 18 28 93 32 60 19 62 74 35 51 4 13 49 42 75 89 97 53 88 20 86
merge sorted: 4 10 11 12 13 14 15 18 19 20 21 28 31 32 33 35 40 42 43 45 46 47 49 51 53 54 55 56 57 59 60 62 64 65 69 70 71 74 75 80 82 84 86 88 89 92 93 94 95 97

小さい順に整列しているのが分かると思います。

処理の過程をグラフのアニメーションにすると、下の動画のような形になります。