マージソート (Merge Sort)

配列を半分に分けて整列し再び併合するマージソートを棒アニメーションで確認。全ケースO(n log n)保証とO(n)追加メモリのトレードオフが分かります。

アルゴリズム

配列

サイズ48
比較中交換/書込ピボット/基準読み整列確定
速度50×

比較

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)の作業領域が必要です。 ソート可視化

よくある質問

クイックソートとの違いは?
クイックは平均的に速い一方で最悪O(n²)の恐れがあります。マージは最悪でもO(n log n)保証+安定ソートです。
なぜ追加メモリが必要?
その場で併合結果を上書きすると未読の値が消えるため、O(n)の一時配列が必要です。

他のアルゴリズム