クイックソート
要素を一つ選び、それより小さいものを左に、大きいものを右に寄せ、両側で同じことを繰り返すソートアルゴリズム。
トニー・ホーアが1959年、25歳のときにモスクワで、機械翻訳の課題のために単語を並べ替えようとして考案した。1961年にCommunications of the ACMで発表されている。平均計算量は O(n log n) だが、最悪では O(n²) になる。ピボットが常に端に当たるとき、たとえば単純なピボット選択で整列済みの入力を処理すると、まさにそうなる。
それでも実際にはマージソートより速いことが多い。インプレースで動き、キャッシュ効率が高く、ほとんどメモリを確保しないためだ。現代の標準ライブラリはイントロソートを採用しており、再帰が深くなりすぎるとヒープソートに、短い区間では挿入ソートに切り替わる。余談だが、2015年にはJavaのTimSort実装に、不変条件の検査に関する実際のバグがあることが証明された。