Timsort: qué es y cómo ordena Python desde 2002

⏱️ Lectura: 9 min

Guido van Rossum anunció el 11 de noviembre de 2026 que Tim Peters, autor del algoritmo Timsort y del Zen de Python (PEP 20), murió el 15 de julio de ese año. Fue Peters quien, mucho antes de escribir cualquiera de los dos, convenció a Van Rossum de que int y float debían mezclarse en una misma operación aritmética, según el anuncio original.

📑 En este artículo

1. El algoritmo Timsort: qué es y de dónde salió
2. Cómo decide Timsort cuándo mezclar las dos técnicas
3. Por qué le importa a quien programa en Python, Java o Android
4. Timsort frente a quicksort, merge sort y el dual-pivot de Java
5. Cuándo Timsort no es la mejor opción
6. El Zen de Python: la otra gran huella de Tim Peters
7. Referencias
   1. 📚 Artículos relacionados

El nombre que millones de programas ejecutan todos los días sin saberlo es el de esa creación: Timsort. Peters lo diseñó en 2002 para ordenar las listas de Python y, según el mismo anuncio de Van Rossum, Java y Android lo adoptaron después para sus propias colecciones.

El algoritmo Timsort: qué es y de dónde salió

Timsort es un algoritmo de ordenamiento híbrido. Combina insertion sort para tramos pequeños con una versión adaptativa de merge sort para el resto de la lista. Desde 2002 es el que corre detrás de list.sort() y sorted() en Python, y también el que usa Java para ordenar arrays de objetos, según el relato de Van Rossum sobre su creador.

La idea de combinar dos técnicas de ordenamiento no es nueva, pero la forma en que Timsort decide cuándo usar cada una sí lo es. En lugar de asumir que los datos llegan en cualquier orden, el algoritmo primero busca runs: tramos de la lista que ya vienen ordenados, ascendente o descendente, por pura casualidad. Los datos reales rara vez son aleatorios. Suelen tener fechas, nombres o IDs parcialmente ordenados, y Timsort explota exactamente eso.

Cómo decide Timsort cuándo mezclar las dos técnicas

El algoritmo recorre la lista de izquierda a derecha y agrupa elementos consecutivos en runs. Si un run es más corto que un umbral mínimo (normalmente entre 32 y 64 elementos, según el tamaño total de la lista), Timsort lo extiende con insertion sort hasta llegar a ese umbral. El insertion sort es lento en listas grandes, pero muy rápido en tramos cortos, y ahí es donde gana.

Cada run terminado se apila en una pila de runs pendientes. Timsort mantiene un invariante sobre los tamaños relativos de esa pila: cada run debe ser más grande que la suma de los dos siguientes. Cuando eso se rompe, mezcla los runs vecinos con una versión de merge sort que usa menos memoria que la clásica.

Si durante varias mezclas seguidas uno de los dos runs «gana» siempre, el algoritmo activa el modo galopante. En vez de comparar elemento por elemento, busca con saltos binarios dónde insertar de una vez un bloque completo del run perdedor. Ese modo galopante es la parte menos intuitiva del diseño y la que más distingue a Timsort de un merge sort de manual.

La nota técnica que Tim Peters escribió para el código fuente de CPython describe el razonamiento completo, incluida la fórmula exacta para calcular el tamaño mínimo de cada run.

flowchart TD
A["Lista de entrada"] --> B["Detectar run ascendente o descendente"]
B --> C{"Run mas corto que el minimo"}
C -- "si" --> D["Extender con insertion sort"]
C -- "no" --> E["Apilar run"]
D --> E
E --> F{"Se rompe el invariante de tamanios"}
F -- "si" --> G["Mezclar runs vecinos con merge sort adaptativo"]
F -- "no" --> H["Seguir leyendo la lista"]
G --> H
H --> I["Lista completamente ordenada"]

Por qué le importa a quien programa en Python, Java o Android

Para quien escribe backend en Python, Timsort es la razón de que ordenar listas de diccionarios, tuplas o registros de base de datos sea rápido incluso cuando esos datos ya vienen casi ordenados, por ejemplo por fecha de creación. No hay que configurar nada: sorted(lista, key=...) ya corre sobre Timsort.

Para quien trabaja en Java o Android, el mismo algoritmo ordena cualquier array de objetos. Si tu equipo usa Collections.sort() o Arrays.sort() sobre un array de objetos, está corriendo Timsort sin saberlo, igual que en Python.

Y para quien diseña estructuras de datos propias, Timsort es un caso de estudio de un principio más general. Optimiza para el caso común de los datos reales en lugar del peor caso teórico. Eso es justo lo que separa a un algoritmo de manual de uno que sobrevive 24 años en producción.

Timsort frente a quicksort, merge sort y el dual-pivot de Java

Ningún algoritmo de ordenamiento gana en todo. La tabla compara Timsort con las tres alternativas más conocidas del mismo problema.

Algoritmo	Estable	Peor caso	Ventaja frente a datos reales	Dónde se usa
Timsort	Sí	O(n log n)	Explota runs ya ordenados; casi gratis en datos parcialmente ordenados	Python list.sort(), Java Arrays.sort() para objetos, Android
Quicksort clásico	No	O(n²)	Rápido en promedio, pero no aprovecha el orden existente	Variantes de qsort en C y en varias stdlib
Merge sort clásico	Sí	O(n log n)	Garantiza el peor caso, pero mezcla aunque los datos ya estén ordenados	Bases para estructuras que exigen estabilidad sin adaptarse al input
Quicksort dual-pivot	No	O(n log n) en promedio	Muy rápido en arrays de primitivos, sin costo de estabilidad	Java Arrays.sort() para tipos primitivos como int y double

La fila que más sorprende suele ser la última, porque Java no usa Timsort para todo. Para arrays de int, double o char usa un quicksort dual-pivot, porque esos arrays no necesitan estabilidad (no hay objetos iguales con identidad distinta que preservar) y el quicksort dual-pivot es más rápido ahí. Timsort se reserva para arrays de objetos, donde la estabilidad sí importa.

Cuándo Timsort no es la mejor opción

Timsort tiene un costo de memoria adicional, porque necesita un buffer temporal para las mezclas. En sistemas con memoria muy ajustada, como microcontroladores, ese costo pesa más que en un servidor backend típico.

Tampoco es la opción más rápida posible para arrays de números primitivos sueltos sin ningún orden previo. Ahí un quicksort bien implementado, sin la contabilidad de runs y sin garantizar estabilidad, puede ganarle. Por eso Java separa los dos casos en lugar de usar Timsort para todo.

Y su comportamiento adaptativo, que es su mayor fortaleza, también complica los benchmarks. El mismo algoritmo puede tardar tiempos muy distintos según qué tan ordenados vengan los datos de entrada, así que comparar Timsort contra otro algoritmo con un solo caso de prueba casi nunca cuenta la historia completa.

El Zen de Python: la otra gran huella de Tim Peters

Mientras diseñaba Timsort, Peters ya era conocido en la lista de correo de Python como «Timbot», según el anuncio de Van Rossum. Respondía preguntas de usuarios con un humor tan constante que se volvió su firma, marcada siempre con <wink>. Ese tono, mitad técnico y mitad informal, es el mismo que atraviesa el Zen de Python, la lista de aforismos que todavía aparece al escribir import this en cualquier intérprete de Python.

El Zen no es un manual de sintaxis: es una guía de criterio. Frases como «explícito es mejor que implícito» o «simple es mejor que complejo» no dictan cómo escribir código, sino cómo discutir una decisión de diseño cuando dos soluciones son técnicamente válidas. Un comentario en Hacker News recuerda, por ejemplo, que el parámetro self explícito en los métodos de Python, a diferencia de Java o C++, se discutió con ese mismo criterio, y que Peters tuvo un rol activo en esa discusión.

Van Rossum resumió la influencia de Peters en una frase de su anuncio: «It’s hard to overestimate Tim’s influence on Python.» Agregó, además, que antes de escribir el Zen, Tim ya lo había convencido de mezclar int y float en una misma operación aritmética, porque es lo que cualquier usuario esperaría. Esa clase de decisiones, pequeñas pero con efecto en millones de programas, es la que el Zen trató de volver repetible para el resto del equipo.

📌 Nota: El anuncio completo, con más anécdotas de otros desarrolladores del núcleo de Python, está en el hilo original de discuss.python.org.

Ninguno de los dos legados depende del otro para seguir vigente. Timsort sigue ordenando listas aunque nadie piense en su autor al escribir sorted(), y el Zen sigue citándose en code reviews aunque quien lo cite no sepa quién lo escribió. Esa es la prueba más clara de qué tan bien diseñados estaban los dos. Sobrevivieron a dejar de necesitar a su autor.

Referencias

• In Memoriam: Tim Peters 1952-2026: anuncio de Guido van Rossum con la fecha de la muerte de Peters y el origen de Timsort.
• listsort.txt en el repositorio de CPython: la nota técnica original de Tim Peters sobre el diseño de Timsort.
• PEP 20: The Zen of Python: el texto completo de los aforismos escritos por Tim Peters.
• Hilo de Hacker News sobre la muerte de Tim Peters: reacciones y anécdotas de la comunidad.

Seguimos el tema en @programacion.

Imagen destacada: Foto de Hitesh Choudhary en Unsplash

Así preparamos cada artículo (fuentes, pruebas y criterio editorial): Cómo trabajamos.