Wir können eine Entscheidungsbaum erzeugen, der anhand von Vergleichen auf die richtige Permutation der Eingabe schließt. Für
![$n$](img12.png)
Zahlen gibt es
![$n!$](img53.png)
Permutationen.
Jeder Binärbaum der Höhe
![$h$](img54.png)
hat höchstens
![$2^{h}$](img55.png)
Blätter. Es gilt
Da
![$n!\geq (\frac{n}{e})^{n}$](img57.png)
können wir
![$\log(n!)$](img58.png)
folgendermaßen abschätzen
Somit haben wir eine Baumtiefe von mindestens
![$n\log(n)$](img52.png)
, was die untere Schranke für Sortierverfahren ist.