Supondo que o pivot escolhido é sempre a mediana, o algoritmo fará
n comparações na primeira partição.
No segundo nível de recursividade
serão feitas duas
partições, cada uma de tamanho n/2; no total
serão também feitas
n comparações. Entretanto, como as
partições são feitas simultaneamente,
o tempo gasto será proporcional a n/2. No terceiro
nível, teremos quatro partições simultâneas,
cada uma de tamanho n/4,
e assim por diante. Desta forma, o tempo total gasto será dado pela soma
Temos portanto um sort com complexidade (para o melhor caso) de
,
melhor do que o limite
de 
para algoritmos sequenciais.