Быстрая сортировка (Quicksort)
Выбрать элемент, отправить всё меньшее влево, всё большее вправо — и повторить то же для обеих половин.
Тони Хоар придумал её в 1959 году, когда ему было 25 и он сидел в Москве, пытаясь отсортировать слова для эксперимента по машинному переводу. Статья вышла в Communications of the ACM в 1961-м. Средняя сложность — O(n log n), худшая — O(n²), и случается она как раз тогда, когда опорный элемент раз за разом оказывается с краю: например, на уже отсортированных данных при наивном выборе опоры.
Несмотря на это, на практике она обычно обгоняет сортировку слиянием: работает на месте, отлично ложится в кэш и почти ничего не выделяет. Современные стандартные библиотеки используют introsort — быструю сортировку, которая при подозрительно глубокой рекурсии переключается на пирамидальную, а на коротких участках — на сортировку вставками. Назидательная сноска: в 2015 году исследователи доказали, что в реализации TimSort в Java была настоящая ошибка в проверке инвариантов.