配列を半分に分けて整列し再び併合するマージソートを棒アニメーションで確認。全ケースO(n log n)保証とO(n)追加メモリのトレードオフが分かります。
アルゴリズム
配列
比較
0
交換/書込
0
ステップ
0/535
読み
0
補助メモリ
0
再帰の深さ
1/1
速度を落として「1ステップ」で疑似コードのハイライトと棒の色を見比べてみてください。
疑似コード
mergeSort(lo, hi)
mid ← (lo+hi)/2
mergeSort(lo,mid) mergeSort(mid+1,hi)
while left & right remain
a[k] ← smaller of the two fronts
copy merged run back
計算量
| 最良 | O(n log n) |
|---|---|
| 平均 | O(n log n) |
| 最悪 | O(n log n) |
| 空間 | O(n) |
| 安定 | ○ |
マージソートは分割統治の代表格です。配列を半分ずつ要素1つになるまで分割し、2つの整列済み区間の先頭同士を比較しながら小さい方から取り出して併合します。
分割の深さがlog n、各段の併合がn要素を一度だけ処理するため、最良・平均・最悪すべてO(n log n)が保証されます。安定ソートですがO(n)の作業領域が必要です。 ソート可視化