Quicksort (III)

Vorteile:

• Wenn $p$ immer nahe beim Median, dann schnelles Sortieren (asymptotisch wie bei Merge-Sort, $\Theta (n \log n)$)
• Dann sogar (um konstanten Faktor) besser als Merge-Sort, weil Elemente in ihren Bereichen verbleiben.

Nachteile:

• nur wenige Zeilen, aber viele Fehlermöglichkeiten!
• Wenn $p$ schlecht gewählt, dann langsames Sortieren (wie Bubble-Sort, $\Theta (n^2)$, für sortierte Eingaben)
• möglicher Ausweg: p = a [zufällig];