Time and Space Complexity

Complejidad Temporal:

• Caso Promedio: O(n log n)
  • Un pivote equilibrado divide el arreglo aproximadamente a la mitad cada vez, lo que resulta en unos log n niveles de trabajo de particionamiento O(n).
• Peor Caso: O(n²)
  • Si el pivote es siempre el elemento más pequeño o el más grande (por ejemplo, un arreglo ya ordenado con el último elemento como pivote), un lado queda vacío cada vez y la recursión alcanza n niveles de profundidad.

Complejidad Espacial:

• O(n) para la versión que construimos aquí, ya que creamos nuevas listas más pequeñas y más grandes en cada paso. El Quick Sort clásico in-place mejora esto a O(log n) de espacio extra.

Resumen:

• Quick Sort es muy rápido en promedio y es un algoritmo de ordenamiento de referencia en la práctica.
• Una mala elección del pivote puede degradarlo a O(n²); las buenas estrategias de pivote (como elegir un elemento aleatorio o la mediana) evitan esto.