はじめに
どんな問題を解決するか
単純な並べ替えは、リストが大きくなると極端に遅くなります。データが2倍になると、作業量は4倍です。マージソートは、問題を解きやすい小さな問題に分けます。そうすることで、作業量の増え方を、データ量の増え方より少し速い程度に抑えます。
身近なたとえ
マージソートは、大きな答案の山を友達と一緒に並べ替えるようなものです。山を半分に分けてそれぞれ友達に渡し、渡された人もまた半分に分け、全員が1枚ずつ持つまで続けます。そのあと2人ずつ組になり、いちばん上の答案を比べて小さいほうから取っていき、ソート済みの山どうしを1つに合わせます。これを繰り返すと、最後にソート済みの山が1つ残ります。
if len(values) <= 1:📄 1枚ならすでにソート済みmerge_sort(values[:middle])✂️ 山を分けてそれぞれ並べ替えるleft[left_index] <= right[right_index]🤝 合わせる:上の小さいほうを取るresult + left[left_index:] + right[right_index:]📚 もう一方の山の残りを加えるマージソートは、リストを半分に分け、それぞれを再帰的に並べ替えてから、ソート済みの2つを1つに合わせます(マージ)。O(n log n) の時間がかかります。
重要なポイント
if len(values) <= 1: return valuesは再帰を止めるベースケースです。merge_sort(values[:middle])とmerge_sort(values[middle:])は2つの半分を並べ替えます。whileループは、どちらかのリストを使い切るまで、leftとrightの先頭のうち小さいほうを取ります。left[left_index:]とright[right_index:]で、残っている値を加えます。残りはすでに順番どおりに並んでいます。<=を使うと、値が同じときは左から先に取るので、等しい値どうしの元の順番が保たれます。
どんな場面で使う?
- 大きなデータを、いつでも見込みどおりの速さで並べ替える。極端に遅くなる最悪ケースがありません。
- 連結リストや、メモリに収まらないほど大きなデータの並べ替え(外部ソート)。
- 多くのアルゴリズムで使われる考え方である分割統治法を学ぶ。
使わなくてよいとき
- ふだんの Python コード:
sorted()は、マージソートと挿入ソートをうまく組み合わせて調整した Timsort をすでに使っています。 - メモリがとても限られている場合:マージソートには、合わせたリストを入れるための余分なメモリが必要です。
Pythonのマージソート(merge sort)のビジュアライザー
O(n log n)再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
実行結果
[3, 9, 10, 27, 38, 43, 82]
コードの解説
再帰関数は、各部分の要素が1つになるまでリストを分割します。要素が1つのリストは常に並べ替え済みとみなせるからです。その後whileループが、2つの部分リストの先頭のうち小さいほうを取り続けて統合します。常にO(n log n)の時間で動き、O(n)の追加メモリが必要です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
残りを加え忘れる
片方を使い切った時点で、もう片方に残っている値が捨てられてしまいます。
return result
return result + left[left_index:] + right[right_index:]
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ