Почему сортировку сравнением нельзя сделать быстрее O(n log n)

Любую сортировку сравнением можно представить бинарным деревом решений с минимум `n!` листьями, а высота такого дерева — не меньше `log₂(n!) = Θ(n log n)` сравнений в худшем случае.

Модель дерева решений

• Внутренний узел — сравнение a[i] < a[j], два исхода — две ветки.
• Лист — итоговая перестановка. Корректный алгоритм обязан различать все n! порядков входа, иначе два разных входа получат одинаковую перестановку.
• Бинарное дерево высоты h имеет не больше 2^h листьев, значит h ≥ log₂(n!).
• По формуле Стирлинга log₂(n!) ≈ n·log₂ n − 1.44·n, то есть Ω(n log n).

Числа для ощущения

• n = 3: 6 перестановок, нужно минимум 3 сравнения (log₂ 6 ≈ 2.58).
• n = 12: 12! ≈ 4.8·10⁸, минимум 29 сравнений в худшем случае.

Что из этого не следует

• Граница про худший (и средний) случай: Timsort и сортировка вставками на почти отсортированных данных делают O(n) — противоречия нет.
• Граница только для модели сравнений: counting/radix sort используют сами значения ключей как индексы и обходят её.
• Та же техника даёт нижнюю оценку для поиска в отсортированном массиве: n + 1 исходов → ⌈log₂(n+1)⌉ сравнений, так что бинарный поиск оптимален.

Коротко для собеседования

Алгоритм, который только сравнивает элементы, должен различить все n! перестановок, а за h сравнений различимо не больше 2^h исходов — отсюда Ω(n log n). Обойти границу можно лишь без сравнений, как counting и radix sort, а на удачных входах вроде почти отсортированных она не мешает.