Почему быстрее n log n нельзя

Про сортировку часто говорят: «быстрее чем $n \log n$ нельзя». Утверждение верное, но неполное — и без второй половины оно противоречит сортировке подсчётом, которая работает за линию.

Разберёмся, что именно доказано.

Что считается сортировкой сравнениями

Договоримся об алгоритме, который узнаёт о данных только через вопросы вида «верно ли, что $a_i < a_j$». Он может как угодно переставлять элементы, но заглянуть внутрь значения — узнать, что там 42, а не 43, — не может.

Под это определение попадают все сортировки из предыдущих статей: пузырёк, вставки, выбор, слияние, быстрая, пирамидальная. Не попадает подсчёт: он не сравнивает элементы между собой, а использует само значение как адрес в массиве счётчиков.

Дерево решений

Проследим за работой такого алгоритма на массиве из $n$ различных элементов. Первый его шаг — какое-то сравнение. В зависимости от ответа он делает второе сравнение, и так далее, пока не выдаст ответ.

Это дерево: узлы — сравнения, две ветви — «да» и «нет», листья — итоговые перестановки.

graph TD
  A["a₁ < a₂ ?"] -->|да| B["a₂ < a₃ ?"]
  A -->|нет| C["a₁ < a₃ ?"]
  B -->|да| D["1 2 3"]
  B -->|нет| E["a₁ < a₃ ?"]
  E -->|да| F["1 3 2"]
  E -->|нет| G["3 1 2"]
  C -->|да| H["2 1 3"]
  C -->|нет| I["..."]

Два наблюдения.

Листьев не меньше $n!$. Входных массивов, различающихся порядком, ровно $n!$ штук, и каждому нужен свой ответ — своя перестановка. Если бы два разных входа приводили в один лист, алгоритм выдал бы для них одинаковый ответ, и для одного из них ответ был бы неверным.

Число сравнений в худшем случае — это глубина дерева. А двоичное дерево глубины $d$ имеет не больше $2^d$ листьев.

Складываем: $2^d \ge n!$, то есть

$$d \;\ge\; \log_2 n!$$

Сколько это

Оценим $\log_2 n!$ грубо, без формул. В произведении $n! = 1 \cdot 2 \cdot \ldots \cdot n$ последняя половина сомножителей — каждый не меньше $n/2$. Значит $n! \ge (n/2)^{n/2}$, откуда

$$\log_2 n! \;\ge\; \frac{n}{2}\left(\log_2 n - 1\right)$$

Это уже $\Theta(n \log n)$. Точная оценка даётся формулой Стирлинга: $\log_2 n! \approx n \log_2 n - 1{,}44\,n$.

Подставим настоящие числа. При $n = 10^5$ получается около $1{,}52 \cdot 10^6$ сравнений — любая сортировка сравнениями сделает не меньше. Это, кстати, и объясняет, почему $n \log n$-сортировки на таких размерах отрабатывают мгновенно: полтора миллиона сравнений процессору не страшны.

Что доказано, а что нет

Доказано: сортировка сравнениями делает $\Omega(n \log n)$ сравнений в худшем случае. Заметьте — в худшем. Про конкретный вход это ничего не говорит: на уже отсортированном массиве вставки справляются за $n$ сравнений, и никакого противоречия нет.

Не доказано ничего про алгоритмы, которые сравнениями не ограничиваются. Отсюда все обходные пути:

• сортировка подсчётом использует значение как адрес и работает за $O(n + C)$;
• поразрядная сортировка смотрит на разряды числа и работает за $O(k \cdot n)$;
• если данные уже почти отсортированы, оценка «в худшем случае» просто не про них.

Мораль практическая: если вам нужен именно полный порядок, данные произвольны и вы умеете только сравнивать — $n \log n$ это потолок, и время лучше потратить на что-то другое. Если хоть одно из трёх условий нарушено, есть куда копать.

Полезное следствие

Из той же оценки следует, что поиск $k$-й статистики — задача проще сортировки. Мы разобрали алгоритм за $O(n)$; если бы можно было отсортировать за линию, отдельный алгоритм был бы не нужен. Нижняя оценка объясняет, почему он нужен: сортировка отвечает на более трудный вопрос и за это платит логарифмом.