Низкая граница для сортировки по сравнению

Сегодня я читал отличную статью Жюльен Уокер о сортировке - Eternal Confuzzled - The Art of Sorting , и одна вещь привлекла мое внимание. Я не совсем понимаю ту часть, где автор доказывает, что для сортировки сравнением мы ограничены Ω ( N · log N ) нижней границей

Нижние границы не как очевидно. Наименьшая возможная граница для большинства алгоритмов сортировки равна Ω ( N · log N ). Это связано с тем, что большинство алгоритмов сортировки используют сравнение элементов для определения относительного порядка элементов. Любой алгоритм, выполняющий сортировку путем сравнения, будет иметь минимальную нижнюю границу Ω ( N · log N ), потому что дерево сравнения используется для выбора перестановки, которая будет отсортирована. Дерево сравнения для трех чисел 1, 2 и 3 может быть легко построено:

  1 

Обратите внимание, как каждый элемент сравнивается с каждым другим элементом, и что каждый путь приводит к действительной перестановке трех элементов. Высота дерева определяет нижнюю границу алгоритма сортировки. Поскольку для корректности алгоритма должно быть столько листьев, сколько существует перестановок, минимально возможная высота дерева сравнения равна log N !, , что эквивалентно Ω ( N · log N ) .

Это кажется очень разумным до последней части (выделенной жирным шрифтом), которую я не совсем понимаю - как log N ! эквивалентно Ω ( N · log N ). Должно быть, я что-то пропустил на курсах CopmSci и не могу получить последний переход. Я с нетерпением жду помощи с этим или ссылки на другие доказательства того, что мы ограничены Ω ( N · log N ), если мы будем использовать сортировку по сравнению.