マージソート
リストを半分に分け、それぞれの半分を並べ替えます。そのあと、並んだ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つ目のリストを使わず、リストそのものの中で並べ替えます。
- 比較中
- 移動中
- 位置が確定
試してみましょう: 同じ値が多いリストを選んでください。2つの値が同じときは左半分の方を先に取るので、同じ値どうしの順番は変わりません。
仕組み
どの部分も値が1つになるまで分け続けます。値が1つなら、もう並んでいます。次に部分を2つずつまとめ直します。両方の先頭の値を比べて小さい方を取る、を繰り返します。アニメーションで上に持ち上がる段は、まとめる間だけ使う追加の場所です。
向いている場面
最悪の場合でも速さが落ちず、同じ値の順番も変えたくないときに向いています。Python と Java も、マージソートを改良した方法を使っています。弱点は、追加のメモリが必要なことです。