Tym samym do dalszego przetwarzania przekazuje się o jeden element mniej, co gwarantuje zakończenie rekurencji.
Złożoność Złożoność algorytmu zależy od wyboru elementu rozdzielającego; jeśli podziały są zrównoważone algorytm jest tak szybki jak sortowanie przez scalanie, czyli w przeciwnym przypadku może działać tak wolno jak sortowanie przez wstawianie Średni czas działania przy losowym wyborze elementu rozdzielającego, dorównuje przypadkowi optymistycznemu.
Przypadek optymistyczny W przypadku optymistycznym, jeśli mamy szczęście za każdym razem wybrać medianę z sortowanego fragmentu tablicy, to liczba porównań niezbędnych do uporządkowania n-elementowej tablicy opisana jest rekurencyjnym wzorem
Dla dużych n:
co daje w rozwiązaniu liczbę porównań (a więc wskaźnik złożoności czasowej):
Równocześnie otrzymuje się minimalne zagnieżdżenie rekursji (czyli głębokość stosu, a co za tym idzie, złożoność pamięciową):
Przypadek przeciętny W przypadku przeciętnym, to jest dla równomiernego rozkładu prawdopodobieństwa wyboru elementu z tablicy:
złożoność jest o 39% wyższa niż w przypadku optymistycznym.