Randomisierter Median-Algorithmus

Algorithmus:
Der Randomisierte Median-Algorithmus:
1. Sortieren von $n^{3/4}$ Elementen mit $O(n \log n)$-Algorithmus
2. Daraus Ableiten von Grenzen $p_1$ und $p_2$
3. Einordnen aller $n$ Elemente gemäß Grenzen in drei Partitionen: vergleiche Element mit je Wahrscheinlichkeit $1/2$ mit $p_1$ bzw. $p_2$, wenn nötig noch mit $p_2$ bzw. $p_1$.
4. Wenn Median gemäß Kardinalitäten der Partitionen in der Mittleren liegt, dann sortieren und Median liefern, sonst neuer Start des Algorithmus.

Komplexität:
Der Randomisierte Median-Algorithmus findet den Median in Average Case $3/2n + o(n)$.