Wir können eine Entscheidungsbaum erzeugen, der anhand von Vergleichen auf die richtige Permutation der Eingabe schließt. Für

Zahlen gibt es

Permutationen.
Jeder Binärbaum der Höhe

hat höchstens

Blätter. Es gilt
Da

können wir

folgendermaßen abschätzen
Somit haben wir eine Baumtiefe von mindestens

, was die untere Schranke für Sortierverfahren ist.