2.6.2 Разрешающее дерево сортировки сравнениями

На рис. 2.8 изображено разрешающее дерево (decision tree), соответствующее сортировке последовательности из трёх элементов с по­мощью алгоритма сортировки вставками.

Рисунок 2.8 – Разрешающее дерево сортировки вставками

Поскольку число перестановок из трёх элементов равно 3! = 6, у дерева должно быть не менее 6 листьев. Поскольку двоичное дерево высоты h имеет не более 2^h листьев, имеем n! ≤ 2^h. Логарифмируя это неравенство по основанию 2 и пользуясь неравенством п! > (п / е)^п, вытекающим из формулы Стирлинга , получаем, что

что и утверждалось. Наилучшее время работы алгоритма сортировки сравнениями есть O(nlog n), причем эта оценка не может быть асимптотически улучшена (т.к. доказано, что нижний предел для любой сортировки сравнениями, не использующей дополнительной информации есть (nlog n)).