Zarówno czas działania algorytmu sortowania szybkiego jak również zapotrzebowanie na pamięć są uzależnione od postaci tablicy wejściowej.
Od tego zależy, czy podziały dokonywane w algorytmie są zrównoważone, czy tez nie, a toz kolei zależy od wybranego klucza podziału.
W przypadku, gdy podziały są zrównoważone, algorytm jest równie szybki jak np. sortowanie przez scalanie. Gdy natomiast podziały są niezrównoważone, sortowanie może przebiegać asymptotycznie tak wolno, jak sortowanie przez wstawianie.
Złożoność algorytmu Quicksort możemy rozpatrywać analizując trzy możliwości:
przypadek optymistyczny- gdy za każdym razem jako klucz podziału wybrana zostaje mediana z sortowanego aktualnie fragmentu tablicy, czyli gdy każdy podział daje równe podzbiory danych. Wówczas liczba porównań niezbędnych do uporządkowania n-elementowgo fragmentu jest rzędu:
