マージソート
リストを半分に分け、それぞれを整列し、併合して戻す。どんな入力でも例外なく O(n log n) である。
1945 年に John von Neumann が記述したもので、現役で動き続ける最古級のアルゴリズムの一つである。併合の段階では、整列済みの二つのリストの先頭要素のうち小さい方を毎回取り出す。これは線形時間で、再帰の深さは log n、その積が保証された計算量になる。
置き換えにくい理由は二つある。一つは安定であること。等しい要素の相対順序が保たれるため、複数のキーで順に整列する際に不可欠である。もう一つは、順次読み取りしか行わないこと。メモリに収まらない巨大データの標準的選択肢であり、ディスクやテープ上の外部ソートは今もマージソートに依拠している。代償は O(n) の追加メモリで、クイックソートはほぼ不要だが最悪時には二乗時間に劣化する。Python と Java の標準ソートが使う Timsort は、内部的にはマージソートのハイブリッドである。