Pythonアルゴリズム

Pythonのマージソート(merge sort)

このレッスンでは、再帰関数を使い、分割統治の考え方でマージソートを実装します。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

単純な並べ替えは、リストが大きくなると極端に遅くなります。データが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:]📚 もう一方の山の残りを加える
1つずつになるまで分けてから、ソート済みの山どうしを合わせて元に戻していきます。
ひと言でいうと

マージソートは、リストを半分に分け、それぞれを再帰的に並べ替えてから、ソート済みの2つを1つに合わせます(マージ)。O(n log n) の時間がかかります。

重要なポイント

  1. if len(values) <= 1: return values は再帰を止めるベースケースです。
  2. merge_sort(values[:middle]) と merge_sort(values[middle:]) は2つの半分を並べ替えます。
  3. while ループは、どちらかのリストを使い切るまで、left と right の先頭のうち小さいほうを取ります。
  4. left[left_index:] と right[right_index:] で、残っている値を加えます。残りはすでに順番どおりに並んでいます。
  5. <= を使うと、値が同じときは左から先に取るので、等しい値どうしの元の順番が保たれます。

どんな場面で使う?

  • 大きなデータを、いつでも見込みどおりの速さで並べ替える。極端に遅くなる最悪ケースがありません。
  • 連結リストや、メモリに収まらないほど大きなデータの並べ替え(外部ソート)。
  • 多くのアルゴリズムで使われる考え方である分割統治法を学ぶ。

使わなくてよいとき

  • ふだんの Python コード:sorted() は、マージソートと挿入ソートをうまく組み合わせて調整した Timsort をすでに使っています。
  • メモリがとても限られている場合:マージソートには、合わせたリストを入れるための余分なメモリが必要です。

Pythonのマージソート(merge sort)のビジュアライザー

O(n log n)

再生またはステップを使って、比較とデータ移動を順に確認できます。

サンプルコード

コードを実行 →
main.py
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. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

残りを加え忘れる

片方を使い切った時点で、もう片方に残っている値が捨てられてしまいます。

問題
return result
修正
return result + left[left_index:] + right[right_index:]

このレッスンを終えましたか?

学習済みにすると進み具合を記録できます。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ