1 歩ずつ動かす
[5, 2, 8, 1, 9, 3, 7, 4] を小さい順に並べる
- 50
- 21
- 82
- 13
- 94
- 35
- 76
- 47
作業用の列 (合わせる前の左右)
- 比較中
- 書いた
- 空き
- 書き終えた (作業用の列)
- いま扱う範囲
- 箱の上の字は、分ける真ん中 (mid)
- 箱の下の数字は添字
1 歩目 / 全 57 歩比べた回数 0 回書き込んだ回数 0 回
8 個の値を小さい順に並べます。半分ずつに分け、並んだ 2 つの列を 1 つに合わせていきます。
いま動いている疑似コードの行
- 1merge_sort(lo, hi) を次のとおり行う
- 2lo >= hi なら何もしない (1 個は並んでいる)
- 3mid = (lo + hi) ÷ 2 (小数は切り捨て)
- 4merge_sort(lo, mid) と merge_sort(mid + 1, hi) を行う
- 5左右の先頭を比べ、小さいほうを配列へ書く (同じなら左)
- 6片方が空になったら、もう片方の残りをそのまま書く
見本を変える
予想してみる
この歩には問題がありません。「1 歩進む」で、次の問題が出るところまで進めましょう。
今回わかること
- 半分に分け、並んだ 2 つの列を 1 つに合わせる流れ
- 入力の並びによらず、計算量が O(n log n) になる理由
前提
- 配列と添字 (0 から数える番号)
- 再帰 (関数が自分を呼ぶ書き方)
- 配列を一時的に別の場所へ写す考え方
どんな並べ方か
マージソートは、配列を半分に分け、それぞれを並べてから、並んだ 2 つの列を 1 つに合わせる並べ方です。分けた先も同じやり方で並べるので、再帰で書きます。
並んだ 2 つの列を合わせるときは、左右の先頭どうしを比べて、小さいほうを書いていくだけです。分ける深さが log n 段で、各段で n 個を書くので、入力によらず n log n に収まります。
手順と具体例
- 1範囲を、真ん中で左右の 2 つに分ける
- 2左と右を、それぞれ同じやり方で並べる (1 個になったら並んでいる)
- 3左右を作業用の列に写し、配列の範囲を空ける
- 4左右の先頭を比べ、小さいほうを配列へ書く (同じなら左)
- 5片方が空になったら、もう片方の残りをそのまま書く
| 区切り | 比べた / 書き込んだ | 終わったときの並び |
|---|---|---|
| 添字 0 から 1 を合わせる | 1 回 / 2 回 | 2, 5, 8, 1, 9, 3, 7, 4 |
| 添字 2 から 3 を合わせる | 1 回 / 2 回 | 2, 5, 1, 8, 9, 3, 7, 4 |
| 添字 0 から 3 を合わせる | 3 回 / 4 回 | 1, 2, 5, 8, 9, 3, 7, 4 |
| 添字 4 から 5 を合わせる | 1 回 / 2 回 | 1, 2, 5, 8, 3, 9, 7, 4 |
| 添字 6 から 7 を合わせる | 1 回 / 2 回 | 1, 2, 5, 8, 3, 9, 4, 7 |
| 添字 4 から 7 を合わせる | 3 回 / 4 回 | 1, 2, 5, 8, 3, 4, 7, 9 |
| 添字 0 から 7 を合わせる | 7 回 / 8 回 | 1, 2, 3, 4, 5, 7, 8, 9 |
比べる回数と計算量
| 場合 | 比べる回数 | 計算量 |
|---|---|---|
| いちばん速い | およそ n log₂ n ÷ 2 回 (もう並んでいる) | O(n log n) |
| 平均 | およそ n log₂ n - 1.25n 回 | O(n log n) |
| いちばん遅い | n log₂ n - n + 1 回 | O(n log n) |
8 個なら、どんな並びでも書き込みは 24 回 (8 × 3 段) です。比べる回数は、もう並んでいれば 12 回、いちばん多くても 17 回で済みます。
使いどころ
向いているとき
- 要素が多く、どんな並びでも安定して速く並べたいとき
- 同じ値の順番を崩したくないとき (安定な並べ方)
- 連結リストや、ファイルのように後ろから読むしかないデータを並べるとき
向いていないとき
- 要素が少なく、作業用の列を用意する手間のほうが大きいとき
- メモリに余裕がなく、配列と同じ大きさの作業用の列を持てないとき
コード
疑似コード
- 1merge_sort(lo, hi) を次のとおり行う
- 2lo >= hi なら何もしない (1 個は並んでいる)
- 3mid = (lo + hi) ÷ 2 (小数は切り捨て)
- 4merge_sort(lo, mid) と merge_sort(mid + 1, hi) を行う
- 5左右の先頭を比べ、小さいほうを配列へ書く (同じなら左)
- 6片方が空になったら、もう片方の残りをそのまま書く
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- buf[left] <= buf[right] を < にすると、何が変わりますか？
- 同じ値のとき右を先に書くので、同じ値どうしの順番が入れ替わります。<= にして左を先に書くから、マージソートは安定な並べ方になります。
- 作業用の列は、なぜ要るのですか？
- 配列へ書きながら左右の先頭を読むと、まだ読んでいない値を上書きしてしまうからです。先に範囲を写しておけば、安心して配列へ書き戻せます。
- クイックソートと比べて、どちらが速いですか？
- 入力によらず n log n に収まるのがマージソートの強みです。クイックソートは平均では速く、作業用の列も要りませんが、基準の選び方が悪いと n² まで遅くなります。
