Algoritmos de ordenación en Python — los 14 explicados con animación

¿Sabes qué algoritmo usa Python cuando llamas a lista.sort()? Casi todo el mundo te dirá “quicksort”. Casi todo el mundo está equivocado.

Lo que Python usa de verdad se llama Timsort, y lo inventó un señor llamado Tim Peters para Python en 2002. JavaScript lo copió en 2018. Java lo copió antes. Y, para ordenar tipos primitivos, Java usa una variante de quicksort llamada Dual-Pivot Quicksort; C++ usa Introsort; Rust y Go usan pdqsort. Es decir: el quicksort puro que te enseñan en clase no lo usa casi ningún lenguaje moderno tal cual.

Esto no es trivia. Detrás hay una historia preciosa de ingeniería: cada algoritmo de ordenación tiene un punto fuerte y un talón de Aquiles, y los lenguajes reales los combinan en híbridos para evitar los peores casos. Si entiendes cuándo cada algoritmo brilla, entiendes por qué los lenguajes los mezclan.

Esta entrada es el pilar del clúster: la mesa donde están todos los algoritmos clásicos de ordenación, su complejidad real, un Reel de cada uno con la animación y los enlaces a la explicación detallada. Más abajo te dejo también la tabla de qué algoritmo usa cada lenguaje, que es lo que la mayoría no encuentra cuando lo busca.

Antes de la tabla: qué quieren decir O, Θ y Ω

Vas a ver tres símbolos repetidos en cualquier comparativa de algoritmos. Si no los conoces, las tablas son un jeroglífico. La idea es muy sencilla:

• O(n²) — pronunciado “O grande de n al cuadrado”. Es la cota superior: en el peor de los casos, el algoritmo hará como mucho del orden de n² operaciones. Es el “techo de cristal” del peor escenario posible.
• Ω(n) — “Omega de n”. Es la cota inferior: en el mejor de los casos hará como mínimo del orden de n operaciones. Es el “suelo” — no puede ir más rápido que eso, ni con la lista perfecta.
• Θ(n log n) — “Theta de n log n”. Cuando la cota superior y la inferior coinciden, decimos que el algoritmo es Θ de esa función. Es el caso típico: ni tan bueno como el mejor, ni tan malo como el peor.

Para que se vea fácil: bubble sort es Ω(n) (mejor caso, lista ya ordenada → una pasada y sale), Θ(n²) (caso medio, lista cualquiera) y O(n²) (peor caso, lista al revés). Mismo algoritmo, tres velocidades muy distintas según la entrada.

En la práctica, cuando alguien dice “este algoritmo es O(n log n)” sin más contexto, suele referirse al caso típico (Θ). Es una imprecisión técnica que casi todo el mundo perdona. Solo importa la diferencia entre los tres cuando algún caso (mejor o peor) se desvía mucho del típico — exactamente lo que pasa con quicksort, cuyo peor caso es O(n²) aunque su caso medio sea O(n log n).

¿Y por qué unos crecen mejor que otros?

Big-O responde a una pregunta: si los datos crecen, ¿cuánto crece el trabajo?

• O(n²) — si doblas el tamaño, el trabajo se multiplica por 4. Bubble, insertion, selection. Bien para listas cortas. Inviable para grandes.
• O(n log n) — si doblas el tamaño, el trabajo apenas crece poco más del doble. Merge, heap, quicksort en su caso medio. La franja de los algoritmos buenos.
• O(n + k) — lineal, donde k es el rango de valores. Counting, radix. Rompen la barrera del O(n log n) cuando k es pequeño porque no comparan, distribuyen.

Para meter números a esto: con 10.000 elementos aleatorios, bubble hace 49.986.222 comparaciones; merge sort hace 120.560. Es 414 veces más trabajo. En tiempo real: 5,4 segundos contra 21 milisegundos. Esa es la diferencia entre O(n²) y O(n log n) traducida a una experiencia humana.

Si quieres profundizar sin matemáticas, te dejo Big-O en Python para entrevistas.

La tabla que ya viniste a buscar

Los 14 algoritmos del clúster, ordenados de peor a mejor, con su Big-O, memoria, estabilidad y un enlace a la explicación detallada (con animación).

Los Reels animados de cada uno los tienes embebidos en su entrada (las celdas son enlaces). Cada vídeo va con su narración, su código Python destacado paso a paso, y el contador en vivo de comparaciones e intercambios para que veas exactamente por qué su Big-O es el que es.

Los clásicos (los que enseñan en todas las facultades)

Los cinco primeros que se ven en cualquier curso, y los que todos deberíamos conocer al dedillo aunque luego usemos sorted(). Cada uno tiene una analogía cotidiana que se queda grabada:

• Bubble sort — ordenar una fila de personas por altura comparando solo a cada una con la de al lado. Sencillo. Lentísimo. Pedagógico.
• Insertion sort — recoger cartas en la mano y colocar cada nueva en su sitio entre las anteriores. Lento en general, rapidísimo cuando ya está casi ordenado. Por eso los híbridos modernos lo usan para tramos pequeños.
• Selection sort — ordenar un cajón de calcetines sacando primero el más pequeño, luego el siguiente, y así. Siempre el mismo número de comparaciones, pase lo que pase.
• Quicksort — repartir un grupo en dos lados según una persona de referencia, el pivote. Súper rápido de media. Su talón de Aquiles: un mal pivote lo arruina.
• Merge sort — juntar dos mazos de cartas ya ordenados mirando la carta de arriba de cada uno. Garantía absoluta de O(n log n), a cambio de memoria extra.

Los mejorados (variantes con un truco extra)

Los que cogen un algoritmo clásico y le añaden un detalle que cambia su comportamiento. Útiles para entender cómo se evoluciona una idea.

• Cocktail sort — bubble bidireccional. En el mismo recorrido sube el mayor al final y baja el menor al principio.
• Comb sort — bubble con un peine: compara elementos separados por un hueco que va menguando. Saca a las tortugas (valores pequeños atrapados al final) mucho antes que bubble.
• Shell sort — insertion sort con saltos. Primero coloca a grandes rasgos, luego afina. Histórico y aún didáctico.
• Gnome sort — versión “tonta” de insertion: avanzas mientras esté bien colocado y, al ver algo descolocado, retrocedes intercambiando hasta resolverlo.

Los serios (los que sí usarías en producción)

Los tres de O(n log n) garantizado. Cada uno con su nicho:

• Heapsort — organiza la lista como un heap (un árbol metido en una caja: el más grande siempre arriba) y va sacando el mayor al final. O(n log n) sin memoria extra, siempre. Por eso muchos lenguajes lo usan como red de seguridad cuando quicksort se atasca (eso es Introsort).
• Merge sort — divide y fusiona. Es estable (preserva el orden de los elementos iguales) y nunca degrada. Pero necesita memoria extra del orden de n.
• Quicksort — el más rápido de media, base de los híbridos modernos. Por sí solo es peligroso (peor caso O(n²)); por eso siempre se combina.

Los no-comparativos (los que rompen la barrera)

Aquí cambia el juego. No comparan: distribuyen. Y por eso pueden ser O(n + k), más rápidos que el O(n log n) teórico mínimo de los comparativos.

• Counting sort — como ordenar votos: cuenta cuántas veces aparece cada valor y luego reescribe la lista en orden. Brutal para enteros con rango pequeño.
• Radix sort — ordena dígito a dígito, de unidades a decenas a centenas. Lo que harías al ordenar fichas por la última cifra del DNI primero.

Su precio: solo funcionan para enteros (o cosas que puedas convertir a enteros) con un rango razonable. Si tu rango es enorme, k domina y dejas de tener ventaja.

Y el campeón: el híbrido inteligente

• Timsort — es lo que pasa cuando alguien (Tim Peters) coge insertion sort y merge sort, y los combina con cabeza: detecta tramos ya ordenados (“runs”) y los fusiona en vez de empezar de cero. Para tramos cortos usa insertion (que es óptimo en pequeño). Para fusionarlos usa merge (que es estable y O(n log n)). Aprovecha que muchas listas reales ya están parcialmente ordenadas — y por eso bate en la práctica al merge puro y al quicksort.

Nota: esto es la versión simplificada. Timsort real tiene optimizaciones llamadas galloping y reglas finas para decidir cuándo fusionar dos runs. Si te pica el gusanillo, está implementado en C en CPython: Objects/listobject.c (busca “TimSort”).

Y ya que mencionamos Timsort, llega la sección estrella.

Qué algoritmo usa REALMENTE cada lenguaje

Esto es lo que casi nadie cubre claro en español. La tabla actualizada:

¿Por qué tanto híbrido? Porque cada algoritmo puro tiene un peor caso indeseable. Los híbridos detectan cuándo va a pasar algo malo y cambian a otro algoritmo. Introsort empieza con quicksort y, si la recursión es demasiado profunda (señal de mal pivote), se pasa a heapsort. pdqsort detecta patrones que harían colapsar a quicksort y reordena el pivote. Timsort parte de la base de que las listas reales ya están parcialmente ordenadas y lo aprovecha.

Conclusión: en producción casi nunca se usa un algoritmo “puro” de los que se enseñan. Lo que se usa son combinaciones cuidadosas diseñadas para que el peor caso nunca aparezca. Es buena ingeniería: medir → entender el caso real → optimizar el camino habitual y proteger del extremo.

Ver en acción con sortlab — números reales sobre los 7 más importantes

Una cosa es leer las tablas. Otra distinta es ver cuánto le cuesta de verdad a cada algoritmo sobre distintas formas de entrada. Para eso construimos sortlab, una librería didáctica con los 14 algoritmos instrumentados (cuenta comparaciones, intercambios, escrituras y cronometra). Esta llamada genera la matriz algoritmos × tipos de entrada:

from sortlab import matriz, formato_tabla

resultados = matriz(
    ["bubble", "insertion", "selection", "quick", "merge", "heap", "tim"],
    ["ordenada", "inversa", "aleatoria", "casi_ordenada"],
    n=100,
)
print(formato_tabla(resultados))

Salida real (n=100):

Algoritmo  Entrada        Comp.  Interc.  Escr.  Tiempo (ms)
---------  -------------  -----  -------  -----  -----------
bubble     ordenada          99        0      0        0.006
insertion  ordenada          99        0     99        0.011
selection  ordenada       4.950        0      0        0.224
quick      ordenada       4.950       99    198        0.303
merge      ordenada         356        0    672        0.093
heap       ordenada       1.081      640  1.280        0.160
tim        ordenada         224        0    296        0.036

bubble     inversa        4.950    4.950  9.900        0.672
insertion  inversa        4.950        0  5.049        0.422
selection  inversa        4.950       50    100        0.233
quick      inversa        4.950       99    198        0.274
merge      inversa          316        0    672        0.089
heap       inversa          944      516  1.032        0.126
tim        inversa        1.566        0  1.790        0.168

bubble     aleatoria      4.940    2.502  5.004        0.493
insertion  aleatoria      2.597        0  2.601        0.222
selection  aleatoria      4.950       96    192        0.239
quick      aleatoria        638      311    622        0.076
merge      aleatoria        555        0    672        0.108
heap       aleatoria      1.041      592  1.184        0.152
tim        aleatoria      1.102        0  1.118        0.123

bubble     casi_ordenada  4.797      341    682        0.277
insertion  casi_ordenada    440        0    440        0.043
selection  casi_ordenada  4.950        5     10        0.233
quick      casi_ordenada  3.784      105    210        0.233
merge      casi_ordenada    458        0    672        0.099
heap       casi_ordenada  1.071      629  1.258        0.162
tim        casi_ordenada    407        0    421        0.050

Lo que se ve aquí (y casi nadie cuenta así):

• Bubble e insertion ganan claramente con ordenada — 99 comparaciones y casi cero trabajo. Pero insertion sigue ganando con casi_ordenada (440 comparaciones); bubble se hunde a 4.797 ahí. Por eso, en el “caso real” (listas parcialmente ordenadas), insertion es muy superior a bubble.
• Selection hace SIEMPRE 4.950 comparaciones, da igual la entrada. Lo único que cambia entre ordenada (5 intercambios) e inversa (50) es cuántos intercambios necesita. Su predictibilidad es absoluta.
• Quicksort se desploma con ordenada e inversa: 4.950 comparaciones (¡igual que selection!). Es el famoso peor caso O(n²) de la variante Lomuto. Con aleatoria brilla: 638 comparaciones. Es exactamente la razón por la que los lenguajes reales usan híbridos.
• Merge sort es el más consistente: entre 316 y 555 comparaciones siempre, y exactamente 672 escrituras sin importar la entrada. Su determinismo se ve clarísimo en la columna de Escr.
• Tim sort gana con ordenada y casi_ordenada (224 y 407 comparaciones, los números más bajos de toda la tabla). Por eso es lo que Python usa de verdad: en producción, las listas casi nunca son aleatorias; suelen estar parcialmente ordenadas.

¿Y cómo crecen con n? Esta es la pregunta del millón:

from sortlab import comparar, formato_tabla
for n in [100, 1000, 10000]:
    print(f"--- n={n} ---")
    r = comparar(["bubble", "insertion", "quick", "merge", "tim"],
                 n=n, tipo="aleatoria")
    print(formato_tabla(r))

Resumen del escalado sobre listas aleatorias:

Bubble tarda 5,4 segundos para 10.000 elementos aleatorios. Quicksort tarda 16 milisegundos sobre la misma entrada. Es 335 veces más rápido. Y la diferencia crece con n: para 100.000 elementos, bubble entraría en cientos de segundos; quick, en unos pocos cientos de milisegundos.

El código completo de sortlab (los 14 algoritmos instrumentados + el medidor + el generador de entradas) y el análisis paso a paso de POR QUÉ cada uno de estos números sale como sale lo construimos despacio en el Python profesional: medir, optimizar y escalar, kata a kata, con cProfile y memory_profiler. El blog te da el QUÉ y el CÓMO; el curso te da el POR QUÉ y el cómo lo aplicas a tu propio código.

La regla rápida (si tuvieras que elegir tú)

• ¿Lista pequeña (n < 50)? Insertion sort. Más rápido que cualquier O(n log n) en pequeño.
• ¿Importa la estabilidad y tienes memoria? Merge sort.
• ¿Importa el peor caso y no quieres memoria extra? Heapsort.
• ¿Quieres rápido en la práctica y no te importa que pueda degradarse? Quicksort.
• ¿Enteros con rango pequeño? Counting o radix.
• ¿Vas a llamar a sorted() en Python? Ya estás usando Timsort, déjalo.

¿Y los grafos y los árboles?

Si quieres seguir el hilo “de array a estructura”, el siguiente bloque natural son los árboles: cómo se ordena con un árbol (tree sort), cómo funcionan los heaps que vimos en heapsort por dentro, y cómo extender la idea a los algoritmos sobre grafos. Pero eso es otra serie.

En resumen

Hay 14 algoritmos de ordenación que merece la pena conocer, no porque vayas a implementarlos en producción (ya hay funciones nativas), sino porque entender sus puntos fuertes y débiles te hace mejor ingeniero. Saber qué algoritmo usa cada lenguaje es lo que separa un dev medio de uno que entiende lo que está pasando bajo el capó.

Si quieres aprender a medir y optimizar tu código de verdad, no solo a recitar Big-O, ese es el camino del curso de El Pythonista. Y si esto te enganchó, te dejo aquí abajo el cheatsheet de optimización (gratis a cambio del email).