En la lección anterior toda la magia de la búsqueda binaria dependía de una premisa: los datos ya estaban ordenados. Esta lección paga esa deuda. Rutalia genera cada día cientos de miles de registros de entrega — al mes, millones — y necesita ordenarlos por (zona, hora) para consolidar rutas, por código postal para paletizar, por peso para tarificar. A esa escala, la diferencia entre un algoritmo O(n²) y uno O(n log n) no es "un poco más lento": es la diferencia entre 3 segundos y varios días. Aquí estudiaremos mergesort y quicksort (los dos grandes divide y vencerás), heapsort (cobrando el heap que construimos en 01-04), la cota inferior Ω(n log n) que ningún algoritmo por comparación puede batir, las ordenaciones sin comparación que sí la baten (counting sort y radix sort), y finalmente Timsort: lo que Python ejecuta de verdad cuando llamas a sorted, y cómo exprimirlo con key= y la estabilidad.

1. Por qué O(n²) no sirve a escala
2. Mergesort: divide y vencerás con garantías
3. Quicksort: partición, pivote y el peor caso
4. Heapsort en breve: el heap de 01-04 puesto a ordenar
5. La cota inferior Ω(n log n): el árbol de decisión
6. Ordenar sin comparar: counting sort y radix sort
7. Timsort: lo que Python usa realmente (sorted, key=, estabilidad)
8. Tabla comparativa final

En 01-01 dibujamos la jerarquía de crecimiento: log n ≪ n ≪ n log n ≪ n². Pongámosle números de Rutalia. Supón ~10⁸ operaciones elementales por segundo (orden de magnitud razonable para Python con constantes pequeñas):

Los algoritmos cuadráticos (burbuja, selección, inserción) no son "malos": la inserción es de hecho excelente para n pequeño o datos casi ordenados, y veremos que Timsort la usa por dentro. Pero como algoritmo principal a escala de los datos de Rutalia están descartados. Necesitamos n log n, y hay tres caminos clásicos para llegar: partir por la mitad (mergesort), partir por un pivote (quicksort) y usar una estructura (heapsort).

La estrategia es la misma que usamos en 01-03 con la recursión: resolver dos mitades y combinar. La operación clave es la mezcla (merge): dadas dos listas ya ordenadas, producir una ordenada en O(n) comparando siempre las cabezas.

Tres observaciones que importan:

• Coste. La recurrencia es T(n) = 2·T(n/2) + O(n): dos subproblemas de tamaño mitad más una mezcla lineal. Por el teorema maestro de 01-02 (caso 2: el trabajo se reparte por igual entre niveles), T(n) = Θ(n log n) — y es así siempre: mejor caso, peor caso y caso medio. Mergesort no tiene sorpresas.
• Estabilidad. El <= de la mezcla hace que, ante empate, gane el elemento de la mitad izquierda — es decir, el que iba antes en la lista original. Dos entregas con el mismo minuto (9) conservan su orden relativo (E-013 antes que E-088). Guarda este concepto: será la pieza central de la sección de Timsort.
• Memoria. Esta versión crea listas nuevas en cada nivel: O(n) de memoria auxiliar. Existe mergesort casi in-place, pero es complejo y raramente compensa; asumir el O(n) extra es el precio estándar. Cuando ni siquiera cabe una copia en RAM (históricos de años), la mezcla se hace por bloques desde disco — eso es la ordenación externa, que desarrollaremos en 06-03.

Quicksort también divide, pero al revés que mergesort: el trabajo se hace antes de recursar, en la partición. Se elige un elemento pivote y se reorganiza el array en tres zonas: menores, iguales y mayores que el pivote. Después, las zonas de menores y mayores se ordenan recursivamente — y no hay nada que combinar, porque la partición ya dejó cada elemento en el lado correcto.

Primero, la versión pedagógica (clara pero con memoria extra):

Y la versión in-place que da fama a quicksort (partición de Lomuto, la más fácil de razonar):

El invariante de la partición (otra vez invariantes, como en 04-01): al acabar cada vuelta del bucle, a[lo..i] contiene solo elementos <= pivote y a[i+1..j] solo elementos > pivote.

Si el pivote parte el array en mitades parecidas, la recurrencia es la de mergesort: Θ(n log n). Pero si el pivote es siempre el mínimo o el máximo, una "mitad" tiene n−1 elementos: T(n) = T(n−1) + O(n) = O(n²). ¿Y cuándo pasa eso con el pivote ingenuo "primer elemento"? Con datos ya ordenados o casi ordenados — exactamente el caso más común en la práctica (el histórico de Rutalia llega casi ordenado por timestamp, con alguna corrección fuera de orden). Un quicksort ingenuo es peor cuanto más fácil parece la entrada.

Mitigaciones, de más simple a más robusta:

Dos apuntes más: la profundidad de recursión también es O(n) en el peor caso (en Python, RecursionError; se mitiga recursando solo sobre la parte pequeña e iterando sobre la grande), y la partición con intercambios no es estable — dos entregas empatadas pueden acabar en orden inverso al original. A cambio, quicksort ordena in-place (O(log n) de pila, sin array auxiliar) y sus constantes son excelentes por su buen uso de la caché: por eso, bien implementado, suele ganar a mergesort en la práctica.

En 01-04 construimos min-heaps con heapq para la cola de reparto prioritario, y en 02-03 y 03-03 los reutilizamos para el mejor-primero y para Dijkstra. Heapsort es la observación de que un heap ya es un algoritmo de ordenación: construye un heap con los n elementos (O(n) con heapify) y extrae el mínimo n veces (n × O(log n)).

Balance: O(n log n) garantizado (como mergesort), in-place en su versión clásica sobre array (la de arriba usa una copia por claridad), pero no estable y con constantes peores que quicksort (los saltos por el árbol del heap castigan la caché). Su papel moderno es de red de seguridad: es el plan B de introsort cuando quicksort degenera. No le dedicamos más espacio porque la mecánica del heap ya la dominas del módulo 1.

Tenemos tres algoritmos O(n log n). Pregunta natural: ¿se puede bajar más? Para algoritmos que solo obtienen información comparando pares de elementos, la respuesta es no, y el argumento es precioso e intuitivo:

1. Un algoritmo de ordenación por comparación es, visto desde fuera, un árbol de decisión: cada nodo interno es una pregunta "¿a[i] < a[j]?" con dos ramas (sí/no), y cada hoja es un resultado final — una permutación concreta de la entrada.
2. Con n elementos distintos hay n! permutaciones posibles, y el algoritmo debe poder producir cualquiera de ellas: el árbol necesita al menos n! hojas (si dos permutaciones distintas llegaran a la misma hoja, el algoritmo se equivocaría en al menos una).
3. Un árbol binario de profundidad d tiene como mucho 2^d hojas. Necesitamos 2^d ≥ n!, o sea d ≥ log₂(n!).
4. Por la aproximación de Stirling, log₂(n!) ≈ n·log₂ n − 1,44·n = Ω(n log n).

La profundidad del árbol es el número de comparaciones en el peor caso. Conclusión: ningún algoritmo por comparación, por ingenioso que sea, baja de Ω(n log n) en el peor caso. Mergesort y heapsort son, en este sentido, óptimos. Es el mismo tipo de resultado "de imposibilidad" que la NP-dureza práctica de 02-02, pero mucho más fuerte: aquí está demostrado sin condiciones.

La letra pequeña es la puerta a la siguiente sección: la cota solo aplica a algoritmos que comparan. Si sabemos algo más sobre las claves, podemos hacer trampa legal.

Si las claves son enteros en un rango pequeño [0, k), no hace falta comparar nada: se cuenta cuántas veces aparece cada clave y se reconstruye la salida. Ejemplo Rutalia: ordenar las entregas del día por zona (9 zonas: la red urbana del módulo 3).

Coste O(n + k): lineal si k = O(n). Con n = 1.000.000 de entregas y k = 9 zonas, es imbatible. La condición de aplicabilidad es dura: claves enteras (o mapeables a enteros) en un rango k pequeño. Ordenar por importe en céntimos hasta 10.000 EUR (k = 10⁶) aún vale; ordenar por timestamp de nanosegundos, no.

¿Y si el rango es grande pero las claves tienen dígitos? Radix sort (LSD, least significant digit) ordena por el dígito menos significativo, luego por el siguiente, etc., usando en cada pasada una ordenación estable (counting sort). La estabilidad es lo que hace que las pasadas anteriores no se destruyan: al ordenar por el segundo dígito, los empates conservan el orden por el primero.

Ejemplo canónico de Rutalia: paletizar por código postal de 5 dígitos.

Coste O(d · (n + b)) con d dígitos en base b. Para códigos postales, d = 5 y b = 10: lineal en n con constante 5. La misma idea ordena enteros de 64 bits en 8 pasadas de base 256 — así ordenan claves numéricas muchas bibliotecas de alto rendimiento. La cota Ω(n log n) no se viola: no estamos comparando, estamos explotando la estructura de la clave.

Cuando escribes sorted(entregas) o entregas.sort(), Python no ejecuta ninguno de los algoritmos de libro anteriores en estado puro: ejecuta Timsort (creado por Tim Peters para CPython en 2002; adoptado después por Java para objetos y por muchos otros lenguajes). Timsort es un híbrido mergesort + inserción diseñado para datos reales, no aleatorios:

• Detecta runs: tramos ya ordenados (ascendentes o descendentes, que invierte). El histórico de Rutalia llega casi ordenado por timestamp: Timsort detecta esos tramos enormes y se limita a mezclarlos. Sobre datos ya ordenados es O(n).
• Inserción para tramos cortos: los runs de menos de ~32 elementos se extienden con ordenación por inserción — el algoritmo O(n²) que descartamos, imbatible en n minúsculo.
• Mezclas inteligentes: apila los runs y los mezcla con reglas que equilibran tamaños, con galloping para saltar bloques cuando una mitad domina.
• Garantías: O(n log n) en el peor caso, O(n) en el mejor, y — crucial — estable.

Moraleja de ingeniería: en Python no reimplementes quicksort para producción. sorted está escrito en C, es adaptativo y estable; tu quicksort en Python puro será decenas de veces más lento. Los algoritmos de esta lección se estudian para entender costes, garantías y cuándo una ordenación especializada (counting/radix, ordenación externa) supera al genérico — no para sustituir a sorted.

Lo que sí usarás a diario es la interfaz. key= recibe una función que extrae la clave de cada elemento (se llama una vez por elemento, no en cada comparación):

La opción B es exactamente el truco de radix sort a nivel de usuario: como sorted es estable, la segunda ordenación no deshace los empates que dejó la primera. Es la técnica imprescindible cuando el criterio secundario no se puede negar (cadenas descendentes, por ejemplo). Y es la razón por la que la estabilidad, que parecía un tecnicismo en mergesort, es una propiedad de primera clase en la práctica.

• Reimplementar la ordenación en producción. El error número uno. sorted (Timsort en C) gana a cualquier implementación tuya en Python puro. Implementa para aprender; despliega la biblioteca.
• Quicksort con pivote fijo sobre datos casi ordenados. El peor caso O(n²) no es teórico: aparece justo con la entrada más habitual. Pivote aleatorio o mediana de tres, siempre.
• Suponer que toda ordenación es estable. sorted de Python lo es; quicksort y heapsort no; numpy.sort por defecto (quicksort) tampoco. Si encadenas criterios con ordenaciones sucesivas, verifica la estabilidad del algoritmo que uses o el resultado será sutilmente incorrecto.
• key= con trabajo caro recalculado. key se evalúa una vez por elemento, lo cual ya es óptimo — pero si la clave requiere parsear una fecha o consultar un dict, extrae ese cálculo si vas a ordenar varias veces (patrón decorate-sort-undecorate si hace falta).
• Usar counting sort con k enorme. O(n + k) es lineal solo si k = O(n). Con claves de 64 bits, el array de conteo no cabe en la memoria de ningún servidor de Rutalia. Para rangos grandes con estructura de dígitos: radix sort.
• Comparar con cmp mental en vez de claves. En Python 3 no existe el parámetro cmp; piensa siempre "¿qué tupla-clave representa mi criterio?" — casi cualquier criterio compuesto se expresa como tupla, con negaciones para invertir campos numéricos.
• Consejo: para datos que "llegan casi ordenados con excepciones" (el histórico de Rutalia tras correcciones manuales), mide antes de optimizar: Timsort ya es casi O(n) en ese caso, y quizá no necesites nada más.

Ejercicio 1 — Consolidación de rutas. Dada una lista de entregas (id, zona, hora, peso) (tuplas), produce el orden de trabajo de Rutalia: por zona alfabética ascendente, dentro de cada zona por hora ascendente, y a igualdad de ambas, el paquete más pesado primero. Resuélvelo de dos formas: (a) con una sola llamada a sorted y una tupla-clave; (b) con ordenaciones sucesivas explotando la estabilidad. Comprueba que coinciden.

Ejercicio 2 — ¿Qué algoritmo elegirías? Para cada escenario de Rutalia, elige el algoritmo más adecuado de la tabla comparativa y justifica en una frase: (a) ordenar 5.000.000 de paquetes por código postal de 5 dígitos; (b) ordenar 40 paradas de una furgoneta por hora comprometida, en un microcontrolador con memoria mínima; (c) ordenar el histórico mensual por timestamp sabiendo que llega ordenado al 99 % con algunas correcciones intercaladas; (d) ordenar 2.000.000 de entregas por zona (9 valores) conservando el orden de llegada dentro de cada zona.

Ejercicio 3 — Mezcla de k rutas (puente con 01-04). Cada una de las k furgonetas de Rutalia devuelve su registro del día ya ordenado por hora. Escribe mezclar_k(listas) que produzca el registro global ordenado en O(N log k), donde N es el total de registros — usa un heap con tuplas (hora, indice_lista, indice_elemento) como en 01-04. ¿Por qué es mejor que concatenar y llamar a sorted? (Pista: piensa en el mejor caso y en la memoria; nota también que esta mezcla k-vías es el corazón de la ordenación externa de 06-03.)

Solución 1:

Detalle a interiorizar en (b): el orden de las pasadas es el inverso a la prioridad de los criterios, y funciona únicamente porque sorted es estable — cada pasada respeta los empates que dejaron las anteriores.

Solución 2:

• (a) Radix sort LSD con counting sort estable por dígito: 5 pasadas O(n), muy por debajo de n log n para n = 5·10⁶. (En la práctica, medir contra sorted: la constante del C compilado a veces gana igualmente.)
• (b) Heapsort (o inserción, con n = 40 casi da igual): O(n log n) garantizado con O(1) de memoria extra; sin array auxiliar de mergesort ni riesgo O(n²) de quicksort.
• (c) Timsort (sorted tal cual): su detección de runs lo hace casi O(n) sobre datos casi ordenados; cualquier esfuerzo adicional es prematuro.
• (d) Counting sort por índice de zona (k = 9): O(n + 9) lineal y estable, que es exactamente el requisito de "conservar el orden de llegada dentro de cada zona".

Solución 3:

Ventajas frente a sorted(concatenación): (1) coste O(N log k) frente a O(N log N) — con k = 20 furgonetas y N = 10⁶, log k ≈ 4,3 frente a log N ≈ 20; (2) es un algoritmo de streaming: puede emitir resultados sin retener las k listas completas en memoria si llegan como flujos, que es justo lo que necesita la mezcla de bloques de la ordenación externa (06-03). En la biblioteca estándar existe ya: heapq.merge(*listas).

Ya tienes el mapa completo de la ordenación: los cuadráticos mueren a escala (aunque la inserción sobrevive como pieza interna), mergesort y heapsort garantizan el n log n que quicksort solo promete en media (y que introsort convierte en garantía combinándolos), y la cota Ω(n log n) del árbol de decisión demuestra que por comparación no se puede hacer mejor — pero counting y radix sort la esquivan legalmente cuando la clave tiene estructura, como los códigos postales o las 9 zonas de Rutalia. Y en el día a día con Python, la respuesta es casi siempre sorted con una buena tupla-clave, apoyándote en la estabilidad de Timsort para componer criterios. Cuando los volúmenes desborden la RAM y haya que ordenar en disco o en varias máquinas, la mezcla k-vías del último ejercicio será la pieza clave — lo veremos en 06-03.

Con buscar (04-01) y ordenar (04-02) dominados sobre datos estáticos, queda el tercer tipo de búsqueda, el más ambicioso: buscar no un valor en un array, sino una solución en un universo de posibilidades — la ruta de reparto entre obstáculos, la secuencia de movimientos que lleva del estado inicial al objetivo. En la próxima lección (04-03) formalizamos los espacios de estados, reencontramos a BFS, DFS y Dijkstra en su versión implícita, y cumplimos por fin la promesa del módulo 3: A*, el "Dijkstra con brújula".