Für die Laufzeit von vergleichsbasierten Sortieralgorithmen ist
Einfach gesagt
Wenn Sortieralgorithmen mit Vergleichen arbeiten, kann ihre Laufzeit nicht schneller sein als
.
Herleitung
Durch einen Vergleichsbaum, Schicht
Die Höhe des Baumes ist eine untere Schranke für jeden vergleichsbasierten Sortieralgorithmus:
Auflösen auf
Umformen mit Stirling-Formel:
Umschreiben:
Anwenden der Logarithmusgesetze:
Wir berechnen die Schranke, d.h.
Anwenden der Logarithmusgesetze: