Aufwandsabschätzung

• In jeder Ebene der Rekursion wird jedes Element betrachtet, d.h. n-Elemente.
• Die Rekursionstiefe hängt davon ab welches Element als Trennelement gewählt wurde. Im besten Fall wird immer genau das tatsächlich mittlere gewählt, dann ist die Rekursionstiege ld (n). Normalerweise wird das gewählte Trennelement nicht genau das mittlere sein, sodaß sich die Rekursionstiefe etwas verschlechtert: ~ 1,4 ld (n).

Daraus folgt der Aufwand .

Wenn zufällig immer das kleinste oder das größte Element als Trennelement auswählt wird, beträgt die Rekursionstiefe ⁿ/₂ und somit der Aufwand .

Sortierdauer