Sortieren

Satz:
Jeder Algorithmus, der $n$ Elemente vergleichsbasiert sortiert, benötigt min. $O(n \log n)$ Vergleiche.

Beweis:
Bei $n$ Elementen gibt es $n!$ mögliche Permutationen, die sich in Form eines Entscheidungsbaumes an den Blättern darstellen lassen. Die inneren Knoten beschreiben dann Vergleiche der Art $a_i < a_j$.
Der Baum hat Tiefe $\geq \log n! = ... = n \log n - O(n)$.
Genau so viele Schritte/Vergleiche sind zum Sortieren im Optimum nötig.

Definitionen:
- Ein Sortieralgorithmus heißt stabil, wenn er die Reihenfolge gleicher Elemente erhält
- Ein Sortieralgorithmus heißt in-place, wenn er keinen zusätzlichen Speicher benötigt