ソートアルゴリズム

比較に基づくソートは、O(n log n) より速くできないことが証明されている。n個の要素には n! 通りの並び順があり、1回の比較で絞り込める候補は半分でしかないからだ。クイックソート、マージソート、ヒープソートはいずれもこの限界に達するが、メモリ使用量、安定性、最悪時の挙動で違いがある。計数ソートや基数ソートは比較をしないことでこの限界を抜けるが、キーが既知の範囲の整数である必要がある。

実際に自作する人はまずいない。標準ライブラリには何十年も磨かれたハイブリッドが入っている。C++のintrosort（再帰が深くなるとヒープソートに切り替えるクイックソート）、PythonやJavaのオブジェクト用Timsort、Rustのpattern-defeating quicksortなどだ。面白いのはどのアルゴリズムかより、どの比較かという点だ。文字列の照合順序は言語ごとに異なり、一貫性のない比較関数は単に順序が誤るだけでなく、未定義動作を引き起こす。