O Quick-Sort, como o Merge-Sort (ordenação por interalação, será explicado em posts posteriores), se baseia no princípio da divisão e conquista mas por possuir uma abordagem diferente não necessita de espaço de memória adicional, o que pode vir a justificar o motivo dele ser mais utilizado do que o Merge-Sort.

Sua desvantagem ocorre quando a divisão do arranjo (que é baseada em comparação) fica muito desbalanceada (Isto ocorre quando: o arranjo está quase ordenado/desordenado ou estar completamente ordenado/desordenado), mostraremos isso no gráfico abaixo.

Mesmo com essa desvantagem é provado que em média seu tempo tende a ser muito rápido [Cormen, 2002], por isso o nome, Ordenação-Rápida (ou Quick-Sort em inglês).

Complexidade

Melhor Caso: Θ(n lg n);
Caso Médio: Tende a ser Θ(n lg n);
Pior Caso: Θ(n²).


Teste


A figura mostra um gráfico do comportamento do Quick-Sort no pior caso. Eixo Vertical: segundos de 0 à 11, Eixo Horizontal: número de elementos de 100.000 à 2.000.000.

Confira também o Quick-Sort Randômico