Heapsort

O(n log n) garantizado (como merge) Y in place (como quicksort). Construido sobre el heap binario.

El array es el árbol

• Los hijos del nodo i viven en 2i+1 y 2i+2 — sin punteros
• Max-heap: todo padre ≥ sus hijos → el máximo en el índice 0
• Construye el heap y luego extrae el máximo n−1 veces
• Cada extracción: manda la raíz al final con un swap y hunde la nueva raíz

Mira crecer la cola ordenada

Máximo naranja → se intercambia hacia la derecha (verde, ordenado), un nuevo máximo sube. In place, sin un segundo array.

Sin caso malo

Aleatorio, ordenado, invertido — todos el mismo tiempo. (Quicksort explotó 141×.)

El mejor Big-O, no el más rápido

• O(n log n) en el peor caso + O(1) de espacio — el único sort con ambas
• Pero hostil al cache (i → 2i+1 → 4i+3 …) → más lento que quicksort
• Construir el heap es O(n), no O(n log n)
• La garantía detrás del fallback de introsort

Para llevar

Heapsort cambia velocidad del día a día por una garantía incondicional. Big-O y realidad se separan. Sigue: ganarle a O(n log n) sin comparar.