O(n*log(n)) и минимальная сложность алгоритмов сортировки

Изучив базовые алгоритмы сортировки (пузырьком, слиянием, быстрая и т.д.), мы обычно запоминаем, что временная сложность эффективной сортировки - O(n*log(n)).

Но в один прекрасный момент мы встречаем, например, поразрядную сортировку и узнаём, что её временная сложность O(n*k), где k (в данном случае количество разрядов) - фиксированное значение для заданного множества элементов.

Что делает поразрядную сортировку особенной? И что объединяет большинство остальных алгоритмов сортировки? Сравнение элементов (в поразрядной сортировке его нет). Именно сравнение элементов определяет минимальную временную сложность любого соответствующего алгоритма - Ω(n*log(n)). Почему это так?

Сортировку массива A длины n можно всегда представить в виде дерева решений, каждым узлом которого будет попарное сравнение элементов массива. Для примера проще всего представить или нарисовать дерево решений для массива длины 3.

Каждый путь от корня к листу такого дерева решений определяет минимальное количество сравнений, которое необходимо выполнить для упорядочивания заданного массива. То есть временная сложность применения такого дерева определяется его высотой. В общем случае дерево решений имеет n! листьев, что соответствует количеству возможных перестановок n элементов массива. Высота такого дерева - log(n!) = log(1) + log(2) + ... + log(n) >= log(n/2) + ... + log(n) >= n/2*log(n/2) = Ω(n*log(n)).

Таким образом, сложность любого алгоритма сортировки, основанного на сравнении - Ω(n*log(n)). Это знание позволяет считать общепринятые алгоритмы сортировки (например, heap sort) с временной сложностью O(n*log(n)) не только достаточно, но и в общем случае максимально эффективными.