最適アルゴリズムの例 (比較ソートにおけるマージソートやヒープソート)

**最適アルゴリズムの例 (比較ソートにおけるマージソートやヒープソート)**は、列を分割し、整列済み部分列をマージする分割統治ソートである。

仕組み

要素数1まで二分し、左右の先頭を比較して小さい方から出力列へ移す。

計算量・性質

すべてのケースでO(n log n)、通常O(n)の補助領域を使い、安定に実装できる。

具体例

[4,1,3,2]を[4,1]と[3,2]へ分け、[1,4]と[2,3]を[1,2,3,4]へ併合する。

限界と注意点

配列版は追加メモリを要し、小規模区間では定数コストが目立つ。