Доказательство (модель дерева решений). Рассмотрим любой алгоритм сортировки, который может опираться только на сравнения пар ключей. Его выполнение на входе из $n$ различных элементов можно представить как двоичное дерево решений: каждый внутренний узел — сравнение двух элементов, каждая ветвь — результат сравнения ($<$ или $>$), листья — завершённые упорядочения входа. Поскольку разные перестановки входа требуют попадания в разные листья, число листьев не меньше числа перестановок, т.е. не меньше $n!$. Если высота дерева равна $h$, то дерево имеет не более $2^h$ листьев, значит
$$2^h\ge n!\Rightarrow h\ge {\log }_2(n!).$$ Оценка ${\log }_2(n!)$. По неравенству Стирлинга или простому неравенству $n!\ge (n/e{)}^n$ получаем
$${\log }_2(n!)\ge n{\log }_2\frac{n}{e}=n{\log }_{2}n-n{\log }_{2}e=\Theta (n\log n).$$ Следовательно высота любого дерева (т.е. число сравнений в худшем случае) имеет нижнюю границу
$$\Omega (n\log n).$$ (Это и есть информационно‑теоретическая нижняя граница для алгоритмов на сравнениях. Для случая возможных равных ключей аналогичный вывод даёт нижнюю границу, зависящую от числа различных перестановок входа — в худшем случае ключи различны, получаем ту же оценку.)
Какие дополнительные предположения позволяют обойти $\Omega (n\log n)$ - Ключи — целые числа из конечного диапазона $\{0,\dots ,k-1\}$. Тогда можно использовать подсчёт (counting sort) за $O(n+k)$, что при $k=O(n)$ даёт $O(n)$.
- Ключи — фиксированная длина битовой строки (слово) длины $w$. Тогда radix sort (с подсчётом по «цифрам») даёт время $O(n\cdot w/b+2^b)$ для разбиения по $b$-битным цифрам; при разумном выборе параметров и при $w=O(\log n)$ это даёт $O(n)$. Иными словами, при ограниченной (полиномиальной по $n$) длине ключа можно сортировать за линейное время на RAM-модели, использующей арифметические/битовые операции.
- Равномерное распределение ключей или ключи из небольших блоков позволяет применить bucket sort, дающий амортизированно $O(n)$ при подходящих предположениях о распределении.
- Если разрешены операции, отличные от сравнений (индексация, арифметика, побитовые операции, хеширование), то появляются некомпаративные алгоритмы, обходящие информационную границу моделей на чистых сравнениях.
Коротко: нижняя граница $\Omega (n\log n)$ верна для любой модели, где единственное допустимое действие — сравнение двух ключей; её можно обойти, если ключи имеют дополнительную структуру (ограниченный диапазон, фиксированная длина битов, известное распределение) или если алгоритм может делать операции сильнее простого сравнения.