マージソート
リストを半分に分け、それぞれの半分を並べ替えます。そのあと、並んだ2つの半分を1つのリストにまとめます。
- 最良 Ω(n log n)
- 平均 Θ(n log n)
- 最悪 O(n log n)
- メモリ O(n)
- 安定
- 追加メモリが必要
用語の意味
- 最良: この方法にとって一番楽な入力のとき、リストのサイズ n に応じて時間がどう増えるか。
- 平均: ふつうの場合に、n に応じて時間がどう増えるか。n² なら値の数が2倍で時間は約4倍。n log n はずっとゆっくり増えます。
- 最悪: 一番難しい入力での増え方。速さが決して落ちてはいけないときに役立ちます。
- メモリ: リストのほかに必要な追加メモリの量。1 なら変数がいくつかだけ、n ならリストのコピー1つ分です。
- 安定: 同じ値どうしが元の順番を保ちます。レコードを1つの項目で並べ替えるときに大切です。
- 追加メモリ不要: 2つ目のリストを使わず、リストそのものの中で並べ替えます。
- 比較中
- 移動中
- 位置が確定
比較回数 書き込み回数
再生を押すと、並べ替えが進むにつれてコストが増える様子を線で表示します
再生を押すか、1ステップずつ進めてください。
スペースキー: 再生・一時停止。左右の矢印キー: ステップ移動。Home キーと End キー: ジャンプ。
試してみましょう: 同じ値が多いリストを選んでください。2つの値が同じときは左半分の方を先に取るので、同じ値どうしの順番は変わりません。
仕組み
どの部分も値が1つになるまで分け続けます。値が1つなら、もう並んでいます。次に部分を2つずつまとめ直します。両方の先頭の値を比べて小さい方を取る、を繰り返します。アニメーションで上に持ち上がる段は、まとめる間だけ使う追加の場所です。
向いている場面
最悪の場合でも速さが落ちず、同じ値の順番も変えたくないときに向いています。Python と Java も、マージソートを改良した方法を使っています。弱点は、追加のメモリが必要なことです。