分割統治法を純粋に遂行”マージソート”
こんにちは！以前の記事で「単純ソート」と呼ばれる O[n2] のアルゴリズムと、それらの計算量の限界について学びました。
そして、その O[n2] の壁を超えるための強力な戦略として分割統治法を紹介しましたね。
単純ソート３種類 その１ ”選択ソート”
選択ソートの仕組みを徹底解説！アニメーションで学ぶ「一番を探す」ソート【ソートアルゴリズム入門】#1
「選択ソート（最大値選択法）」の仕組みとは？「未ソート領域から最大値を選び、末尾に配置する」という直感的な動きを、インタラクティブなツールで体感。0.2秒ごとに最大値を自動探索するアニメーションで、探索→交換のステップを分かりやすく解説します。
一つ前の記事 “分割統治法”について理解する
分割統治法とは？高速なソートアルゴリズム【ソートアルゴリズム入門】#5
「分割統治法」とは？ 難しい問題を「小さく分けて、後で合体する」ことで高速に解くアルゴリズム戦略です。O(N^2)の壁を破るO(N log N)の鍵となる、マージソートやクイックソートの基本思想を図解します。
今回は、前回紹介した分割統治法を、
最も素直に、そして美しく実装した代表的な高速ソートアルゴリズム、「マージソート（Merge Sort）」の仕組みを解説します。
マージソートの実行例 アニメーション
マージソートの実行例 アニメーション
1. マージソート（Merge Sort・併合ソート）とは？
マージソートは、「分割統治法」に基づき、「とにかく半分に分割していき、後から賢く並べながら結合（マージ）する」アルゴリズムです。
賢く並べるソートというと挿入ソートなどが思い浮かぶかと思いますが、挿入ソートが「整列済みの手札に1枚ずつ”挿入”する」イメージだったのに対し、マージソートは全く違うアプローチを取ります。
2. マージソートの分割統治方法
例として、トランプ12枚1(A)からＱまでをマージソートの方法で並び替える例をもとにマージソートのアルゴリズムを紹介します。
(1)分割
まずは分割です。今の分割グループを半分に分けられなくなるまで分割します。ただし、枚数が奇数なら前のグループが１枚多くなるように分けるものとします（これはどっちでも最終的に結合するのであまり気にしなくてかまいません。）
ステップ１
ステップ２
ステップ３
横並びだと画像にしずらかったので位置をグループごとに並び替えていますが、マージソートは小さい問題に分割していく方法なので並列処理できます。
ステップ４
１枚のグループはもう分割できないので分割終了(色を変えています)。
ステップ５（完了）
これ以上分割できないので分割完了
(2)統治
分割にて、すべてのグループの枚数が１枚になっているので、すでに統治完了しています。
(3)結合
マージソートの「結合（マージ）」操作とは、すでに（昇順で）ソート済みの2つのグループを、1つの大きなソート済みグループにまとめる操作です。
各グループはソート済みなので、「一番小さい要素は、必ずグループの先頭にある」という重要な特性があります。
この特性を利用し、両グループの先頭の要素同士を比較します。そして、より小さい方を新しいグループに順に詰めていきます。これを繰り返すだけで、効率的に2つのグループを1つに結合できます。
実際に結合操作を見ていきましょう。分割の手順を逆にたどりながら結合操作していきます。
逆順で結合 分割のステップ４
一つ前の画像で左上にある一番初めのグループについて、最後の分割を結合操作してみます。最後に分割したのは”９”と”６”です。
(鍵括弧の数字は今属しているグループでの順番です。)
一枚しかないので、それぞれを比較します。9と6なので [6,9]になるように結合します。
結合後のグループでは、１枚目”６”、二枚目”９”になりました。
逆順で結合 分割のステップ３
次に、最後から２番目の分割をたどります。この時、各々のグループの先頭から比較していきます。
先ほどの結合で ”9″と”6″は[6,9]というグループになりました。これと”Q”を結合します。
- 先頭は”６”と”Ｑ”です。Ｑと６だと６が小さいので、６を結合後のグループの先頭にします、Ｑはまだ位置が確定していないので、次に回します。
- １枚目で余ったＱ(残ったカードのなかでは先頭にある)と二番目の９を比較します。９の方が小さいので９を採用します。
- 最後に余ったのはＱなので結合します。
逆順で結合 分割のステップ２
同様にほかのグループもステップ３までさかのぼって結合して、ステップ２の結合をします。
ステップ３の結合と同様に各グループの先頭から比較します。
- ”6″と”1″を比較 ”1″を一番初めに確定、”6″が余る。
- まだ結合されていないグループは、[6,9,Q]と[2,3]になります。
次に、残っているグループの先頭を比較します。
- ”6″と”2″を比較 ”2″を確定、”6″が余る。
- まだ結合されていないグループは、[6,9,Q]と[3]になります。
同様に、残っているグループの先頭を比較します。
- ”6″と”3″を比較 ”3″を確定、”6″が余る。
- まだ結合されていないグループは、[6,9,Q]だけになります。
片方のグループが全部確定しました、この時点で、残っているグループは前の手順で並んでいるので、そのまま最後にくっつけます。
よって結合後は [1,2,3,6,9,Q]となりました。
逆順で結合 分割のステップ１
ステップ２と同様にグループの先頭から比較し結合、どちらか片方のグループをソートし終わるまで繰り返します。ステップ２の時とすることは同じです。
[1,2,3,6,9,Q]と[4,5,7,8,10,j]のグループなので、
- ”1″と”4″を比較 ”1″を確定、”4″が余る。
- まだ結合されていないグループは、[2,3,6,9,Q]と[4,5,7,8,10,j]
：
：
(以下同様なので省略します。)
最後まで結合終わったら、ソート完了です。
3. マージソートの動きを見てみよう！
マージソートで並び替えを試せます。ステップ実行ボタンを押して、並び替えを進めてみてください。
色が濃い部分が今処理をしているグループです。
マージソートの疑似コード(ソートの手順)
手元で試せる環境があったら自身の慣れているプログラミング言語で以下の処理を書いてみると理解が深まると思います。
// L: ソートしたいリスト
algorithm MergeSort(L) is
n ← length of L
// (1) 再帰の停止条件: 要素が1つ以下なら、ソート済みなのでそのまま返す
if n <= 1 then
return L
// (2) 分割 (Divide)
mid ← n / 2 // リストの真ん中
left ← Lの 0 から mid-1 まで
right ← Lの mid から n-1 まで
// (3) 統治 (Conquer)
// 分割した left と right を、それぞれ再帰的にソートする
left_sorted ← MergeSort(left)
right_sorted ← MergeSort(right)
// (4) 結合 (Combine)
// ソート済みの2つをマージして返す
return Merge(left_sorted, right_sorted)
end
// left, right: 2つの「ソート済み」リスト
algorithm Merge(left, right) is
result ← 空のリスト
// left と right の両方に要素が残っている間
while length of left > 0 and length of right > 0 do
// 両者の先頭を比較し、小さい方を result に移す
if left[0] <= right[0] then
result.append( left[0] )
left.remove_at(0) // 先頭を削除
else
result.append( right[0] )
right.remove_at(0) // 先頭を削除
end
end
// (この時点で left か right のどちらかは空になっている)
// left に残った要素をすべて result に追加
while length of left > 0 do
result.append( left[0] )
left.remove_at(0)
end
// right に残った要素をすべて result に追加
while length of right > 0 do
result.append( right[0] )
right.remove_at(0)
end
return result
endまとめ
- マージソートは、「分割統治法」の代表的なアルゴリズム。
- 「分割フェーズ（ひたすら半分にする）」と「結合フェーズ（ソートしながら合体）」で動作する。
- データの状態に関わらず、常に O(n log n) の計算量を保つ、非常に安定した高速なアルゴリズム。
- （弱点として、ソート済みのリストを一時的に保持するための余分なメモリ領域が必要になる）
この O(n log n) という計算量に出てきた「log」とは何でしょうか？
次は、このアルゴリズムの速さの秘密である「log（ログ）」について、なぜ分割統治法で登場するのかを解説します。理解しているという場合は、理解度に合わせて、適宜以降の記事を参照してください。
次の記事 イメージを掴もう(計算量のlogはなぜ？ 高速化の秘密)
なぜ計算量がn log(n)？”log”が出てくる訳をわかりやすく紹介【ソートアルゴリズム入門】#7
O[n^2] を超える高速なソート（クイックソート等）は O[n log n] と呼ばれます。なぜ突然log（対数）が出てくるのか？ その秘密は「半分に分ける」という最強の戦略「分割統治法」にありました。log の正体を視覚的に解き明かします。
次の次の記事 数学的に計算量のlogはなぜ？
なぜ計算量がn log(n)？分割統治法の計算量を数学的に導く【ソートアルゴリズム入門】#8
高速なアルゴリズムに出てくる「n log n」。この計算量を「漸化式（ぜんかしき）」という数学の手法で証明します。「log(n)はどこから来たの？」という疑問を、式を展開しながら中学生にも分かるように解き明かします。
分割統治法を利用した別のアルゴリズム：クイックソート
クイックソートの仕組みを徹底解説！アニメーションで学ぶ「圧倒的平均最速」ソート【ソートアルゴリズム入門】#9
分割統治法を使ったソートの王道”クイックソート” 以前の記事で、分割統治法を用いたアルゴリズムとして、常に安定した \(O(n \log n \) の性能を誇る「マージソート」を紹介しました。 マージソートは「分割は単純 […]
ここまで読んでいただきありがとうございます。
では、次の記事で。 lumenHero
