Time and Space Complexity

Complexidade de Tempo:

• Caso Médio: O(n log n)
  • Um pivô balanceado divide o array aproximadamente ao meio a cada vez, resultando em cerca de log n níveis de trabalho de particionamento O(n).
• Pior Caso: O(n²)
  • Se o pivô for sempre o menor ou o maior elemento (por exemplo, um array já ordenado com o último elemento como pivô), um lado fica vazio todas as vezes e a recursão atinge n níveis de profundidade.

Complexidade de Espaço:

• O(n) para a versão que construímos aqui, pois criamos novas listas menores e maiores a cada passo. O Quick Sort in-place clássico melhora isso para O(log n) de espaço extra.

Resumo:

• O Quick Sort é muito rápido em média e é um algoritmo de ordenação de referência na prática.
• Uma escolha ruim de pivô pode degradá-lo para O(n²); boas estratégias de pivô (como escolher um elemento aleatório ou a mediana) evitam isso.