Ein Entscheidungsbaum modelliert alle möglichen Vergleichsergebnisse eines Sortieralgorithmus.
Blätter entsprechen möglichen Permutationen. Daraus folgt die untere Schranke Ω(nlogn)\Omega(n\log n)Ω(nlogn) für vergleichsbasiertes Sortieren.