Изменения

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

<br>Внутренний узел, помеченный как <tex> i:j </tex>, указывает сравнение между <tex> a_{i} </tex> и <tex> a_{j} </tex>. Лист, помеченный перестановкой <tex> \left \langle \pi(1), \pi(2), \dots , \pi(n) \right \rangle </tex>, указывает упорядочение <tex> a_{\pi(1)} \leqslant a_{\pi(2)} \leqslant \dots \leqslant a_{\pi(n)} </tex>.]]