Изменения

{{Определение|definition=Сортировка сравнениями {{---}} алгоритм сортировки, который совершает операции сравнения элементов, но никак не использует их внутреннюю структуру.}}

|proof=Любому алгоритму сортировки сравнениями можно сопоставить дерево. В нем узлам соответствуют операции сравнения элементов, ребрам {{---}} переходы между состояниями алгоритма, а листьям {{---}} конечные перестановки элементов (соответствующие завершению алгоритма сортировки). Необходимо доказать, что высота такого дерева для любого алгоритма сортировки сравнениями не меньше чем <tex>O\Omega(n \log n)</tex>, где <tex>n</tex> {{---}} количество элементов.

Пусть алгоритм сортирует перестановку из <tex>n</tex> элементов. При сравнении некоторых двух элементовиз них, существует два возможных исхода (<tex>a_i < a_j</tex> и <tex>a_i \geq > a_j</tex>), значит, каждый узел дерева имеет не более двух сыновей. Всего существует <tex>n!</tex> различных перестановок <tex>n</tex> элементов, значит, число листьев нашего дерева не менее <tex>n!</tex> (в противном случае некоторые перестановки были бы не достижимы из корня, а, значит, алгоритм не правильно работал бы на некоторых исходных данных).