Изменения

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