Schnelle vergleichsbasierte Sortieralgorithmen

Algorithmus:
Beim Heap Sort werden die Arrayelemente als Binärer Heap impliziert, so dass Element $a[i]$ die Kinder $a[2i]$ und $a[2i+1]$ hat. Zunächst werden alle Elemente durch Versickern, also ggf. Vertauschungen zu den Blättern hin, einsortiert. Anschließend liefert ein fortgesetztes ExtractMin die sortierte Reihenfolge, Aufwand immer $O(n \log n)$.

Algorithmus:
Beim Merge Sort werden zunächst einzelne Elemente zu sortierten Zweiergruppen verschmolzen, dann jeweils Zweiergruppen zu Vierergruppen usw., Laufzeit gesamt immer $O(n \log n)$.
Beim Verschmelzen werden zwei sortierte Arrays $A$ und $B$ mit getrennten Zählern $i$ und $j$ so durchlaufen, dass immer das kleinere Element der Arrays $min\{ A[i],B[j] \}$ an den neuen Array gehängt und der entsprechende Zähler erhöht wird, lineare Laufzeit!

Algorithmus:
Bei Quicksort [Hoare] werden die Elemente in Partitionen ''$<a$'', ''$=a$'', ''$> a$'' unterteilt und rekursiv sortiert. Das Element $a$ ist erstes Element der Eingabe und heißt Pivotelement.

Analysen:
- Best Case: $\log n (n+1)$, also etwa $n \log n$
- Worst Case: Eingabe vorsortiert, $O(n^2)$
- Average Case: $1.386 n \log n$
- Speicherplatz: kein zusätzlicher Speicher erforderlich, aber instabil

Verbesserungen:
- Hybridverfahren: Für $n \leq 10$ ist Insertion Sort schneller, also Quicksort abbrechen und Insertion Sort verwenden
- Median of 3-Quicksort: Pivotelement als arithmetisches Mittel aus erstem, mittlerem und letztem Wert, Average Case $1.188 n \log n$
- Randomized Quicksort: Average Case $1.386 n \log n$, aber Worst Case tritt nur mit Wahrscheinlichkeit 1/n! ein