Como se puede suponer, la eficiencia del
algoritmo depende de la posición en la que termine el pivote elegido.
- En el mejor caso, el pivote termina en el centro de la lista,
dividiéndola en dos sublistas de igual tamaño. En este caso, el orden
de complejidad del algoritmo es O (n·log n).
- En el peor caso, el pivote termina en un extremo de la lista. El orden
de complejidad del algoritmo es entonces de O(n²).El peor caso dependerá
de la implementación del algoritmo, aunque habitualmente ocurre en listas
que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende
del pivote, si por ejemplo el algoritmo implementado toma como pivote
siempre el primer elemento del array, y el array que le pasamos está
ordenado, siempre va a generar a su izquierda un array vacío, lo que es
ineficiente.
- En el caso promedio, el orden es O(n·log n).
No es extraño, pues, que la mayoría de
optimizaciones que se aplican al algoritmo se centren en la elección del
pivote.
