Zunächst einmal proportional zur Zahl der sortierenden Daten, wie bei jedem Sortierverfahren.
Zusätzlichen Speicher benötigt man für lokale Variable. Diese sind aber hier im Gegensatz zum Straight Selection Sort nicht konstant, sondern wegen der Rekursion abhängig von der Anzahl n der Daten und damit der Ordnung.
Eine Rekursion wird immer dann ausgeführt, wenn nach der Zerlegung die Teilabschnitte noch mehr als ein Element enthält. Ist die Zerlegung optimal (best case), so entstehen zwei gleichlange Teile, und es sind maximal log2n Rekursionen durchzuführen. Bei ungünstiger Verteilung (worst case) kann es allerdings auch zu n-1 Rekursionen kommen; das tritt immer dann auf, wenn der rechte Teilabschnitt immer genau ein Element und der linke Teilabschnitt alle anderen enthält.
Zunächst einmal spielen hier erneut die Anzahl der Wiederholungen eine entscheidende Rolle.
Die eine Schleife ist hier die Zerlegung des betrachteten Abschnitts. Dabei wird jedes Element mit dem Pivot-Element verglichen. Es entsteht ein zeitlicher Aufwand der proportional zur Zahl der Elemente n ist.
Die andere Schleife versteckt sich in der Rekusion: im best case ist der Zeitaufwand hier proportinal zur Rekusionstiefe von log2n und im worst case proportional zu n.
Insgesamt ergibt sich ein Zeitaufwand von
| best case: O(n × log2 n) | worst case: O(n2) |
© Ralph-Erich Hildebrandt, 12. Dezember 2004