Informatik

Welche untere Schranke gilt für vergleichsbasiertes Sortieren?

Jeder vergleichsbasierte Sortieralgorithmus benötigt im Worst Case $\Omega(n\log n)$ Vergleiche.

Grund: Es gibt $n!$ mögliche Ordnungen und ein Vergleich liefert höchstens ein Bit Entscheidungsinformation.