Quicksort
Particiona alrededor de un pivote: menores a la izquierda, mayores a la derecha.
Recursa en cada lado. In place, sin merge.
La partición es LA operación
- Escoge un pivote; recorre; los elementos chicos hacen swap a la izquierda de una frontera
- El pivote cae en su posición final ordenada
- Recursa en los dos lados
- O(n log n) promedio, in place — normalmente el sort más rápido
Mira la partición
Pivote morado · amarillo compara · azul = más chico · verde = ya colocado.
El pivote lo es todo
Pivote de último elemento con input ordenado = O(n²). 141× más lento en n=4000.
Doma el peor caso
- Aleatoriza el pivote → el mal caso esencialmente nunca ocurre
- O mediana de tres, o introsort (caer de vuelta a heapsort)
- Nunca lances a producción un pivote de posición fija
Para llevar
El sort in place más rápido — si cuidas el pivote.
Promedio O(n log n), peor caso O(n²). Sigue: heapsort — O(n log n) garantizado Y in place.