Daraus ergibt sich
. Diese Komplexität
gilt auch für den durchschnittlichen Fall; es lässt sich
zeigen, dass die Zahl der Schritte
nur um den konstanten Faktor 1.4 wächst.
Im ungünstigsten Fall (bei entarteten Partitionen) gilt
.
Source:
QuickSortTest.java
JavaDoc:
QuickSortTest.html
Applet: