Insertion sort en Python — explicado paso a paso (con animación)

Insertion sort es el algoritmo que hace lo mismo que tú cuando ordenas cartas en la mano: coges la siguiente y la deslizas hacia la izquierda hasta dejarla en su sitio entre las que ya tienes ordenadas. Sencillo, didáctico y, sorpresa, rapidísimo cuando la lista ya está casi ordenada — por eso los algoritmos modernos lo usan por dentro para tramos pequeños.

Esta entrada cubre el algoritmo en serio: cómo funciona paso a paso, implementación en Python, JavaScript y Java, su complejidad real, cuándo lo bate todo y por qué Timsort (el que Python usa de verdad) lo lleva dentro como pieza.

Si quieres el panorama de los 14 algoritmos del clúster y qué usa cada lenguaje de verdad: Algoritmos de ordenación en Python — los 14 explicados.

Insertion sort en una frase

Mantén una “parte ordenada” a la izquierda que crece de uno en uno. Para cada elemento nuevo, deslízalo hacia la izquierda mientras sea menor que su vecino, hasta encontrar su sitio. Repite hasta el final.

Aquí lo tienes funcionando sobre 12 valores, con los contadores de comparaciones e intercambios en vivo:

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

En las tablas verás tres símbolos: O, Θ y Ω. Idea rápida:

• O(n²) — “O grande”, cota superior (peor caso). “Como mucho hará del orden de n².”
• Ω(n) — “Omega”, cota inferior (mejor caso). “Como mínimo, n operaciones.”
• Θ(n²) — “Theta”: superior e inferior coinciden. Es el caso típico.

Insertion sort es Ω(n) (mejor caso: lista ya ordenada, una pasada y termina), Θ(n²) (caso medio) y O(n²) (peor caso: lista al revés). Explicación más larga en el pilar del clúster.

Cómo funciona — traza paso a paso

Ordenamos [3, 1, 4, 1, 5] a mano.

Asumimos que el primer elemento (3) ya está “ordenado” (una lista de un elemento siempre lo está). Vamos elemento a elemento:

i = 1, tomamos 1:
– ¿3 > 1? Sí → desplaza/intercambia → [1, 3, 4, 1, 5].
– Llegamos al inicio → para. La parte ordenada ya es [1, 3].

i = 2, tomamos 4:
– ¿3 > 4? No → ya está en su sitio. La parte ordenada: [1, 3, 4].

i = 3, tomamos 1:
– ¿4 > 1? Sí → intercambia → [1, 3, 1, 4, 5].
– ¿3 > 1? Sí → intercambia → [1, 1, 3, 4, 5].
– ¿1 > 1? No → para. Parte ordenada: [1, 1, 3, 4].

i = 4, tomamos 5:
– ¿4 > 5? No → ya está en su sitio.

Total: 4 comparaciones, 3 intercambios para 5 elementos. Compara con bubble (9 y 4 en el mismo ejemplo). Hace menos comparaciones porque cuando un elemento ya está en su sitio, para inmediatamente en vez de seguir hasta el final como bubble.

Implementación en Python

Versión por intercambios (es la que produce una animación limpia y la que ves en el Reel):

def ordenar(lista: list[int]) -> list[int]:
    n = len(lista)
    for i in range(1, n):
        j = i
        while j > 0 and lista[j - 1] > lista[j]:
            lista[j - 1], lista[j] = lista[j], lista[j - 1]
            j -= 1
    return lista


if __name__ == "__main__":
    print(ordenar([3, 1, 4, 1, 5]))  # [1, 1, 3, 4, 5]

Hay también la versión clásica con desplazamientos (más eficiente porque solo hace una asignación por elemento desplazado, no dos):

def ordenar(lista: list[int]) -> list[int]:
    for i in range(1, len(lista)):
        actual = lista[i]
        j = i - 1
        while j >= 0 and lista[j] > actual:
            lista[j + 1] = lista[j]
            j -= 1
        lista[j + 1] = actual
    return lista

Ambas son O(n²) en el peor caso y O(n) en el mejor; la versión con shifts tiene menos asignaciones, así que se considera “la canónica” en producción.

En entrevistas, menciona ambas versiones. Demuestra que entiendes la diferencia entre “intercambiar” y “desplazar” — son conceptos distintos y los entrevistadores notan la diferencia.

Implementación en JavaScript

function ordenar(lista) {
  for (let i = 1; i < lista.length; i++) {
    const actual = lista[i];
    let j = i - 1;
    while (j >= 0 && lista[j] > actual) {
      lista[j + 1] = lista[j];
      j--;
    }
    lista[j + 1] = actual;
  }
  return lista;
}

console.log(ordenar([3, 1, 4, 1, 5])); // [1, 1, 3, 4, 5]

Versión con shifts, equivalente a la canónica de Python.

Implementación en Java

public static void ordenar(int[] lista) {
    for (int i = 1; i < lista.length; i++) {
        int actual = lista[i];
        int j = i - 1;
        while (j >= 0 && lista[j] > actual) {
            lista[j + 1] = lista[j];
            j--;
        }
        lista[j + 1] = actual;
    }
}

Misma estructura. Java necesita int explícito para la variable actual.

Complejidad — por qué brilla con listas casi ordenadas

Métrica	Mejor caso	Caso medio	Peor caso
Tiempo	Ω(n)	Θ(n²)	O(n²)
Memoria	O(1)	O(1)	O(1)
Estable	Sí	Sí	Sí

El mejor caso O(n) aparece cuando la lista ya está ordenada: cada elemento hace una sola comparación (con su vecino izquierdo) y para. Un recorrido lineal, nada más.

El peor caso O(n²) aparece cuando está ordenada al revés: cada elemento tiene que viajar hasta el principio, así que la cantidad total de desplazamientos es 1 + 2 + … + (n-1) ≈ n²/2.

La clave práctica: en el “caso real” —listas parcialmente ordenadas con unos pocos elementos fuera de sitio— insertion sort se acerca al mejor caso. Cada elemento descolocado se mueve solo unas pocas posiciones. Por eso es tremendamente eficiente para listas pequeñas o casi ordenadas.

Por qué es estable: la condición del while es > estricto, así que dos elementos iguales nunca se mueven uno respecto al otro. Conserva el orden original.

Ver en acción — insertion sort sobre 10 listas fijas

Todo el clúster usa las mismas 10 listas fijas (n=15) para que se pueda comparar honestamente entre algoritmos. Aquí están:

#	Nombre	Qué es
1	ordenada	1, 2, 3, ..., 15
2	inversa	15, 14, ..., 1
3	casi_ordenada	1..15 con un par de swaps
4	muy_desordenada	Patrón min-max alternado [1, 15, 2, 14, 3, ...]
5	duplicados	Enteros del rango [1..5] repetidos
6-10	aleatoria_s1 .. aleatoria_s5	5 permutaciones aleatorias deterministas

Aplicamos insertion sort sobre las 10:

from sortlab import bench_estandar, formato_tabla
print(formato_tabla(bench_estandar("insertion", n=15)))

Salida real (tiempo es el mejor de 5 mediciones; Caso y Θ observada los deduce la librería):

Lista            Comp.  Interc.  Escr.  Tiempo (ms)   Caso  Θ observada
---------------  -----  -------  -----  -----------  -----  -----------
ordenada         14           0     14        0.002  Mejor         Θ(n)
inversa          105          0    119        0.012   Peor        Θ(n²)
casi_ordenada    31           0     31        0.004  Mejor   Θ(n log n)
muy_desordenada  63           0     63        0.007  Medio   Θ(n log n)
duplicados       53           0     53        0.006  Medio   Θ(n log n)
aleatoria_s1     74           0     76        0.008  Medio   Θ(n log n)
aleatoria_s2     64           0     68        0.007  Medio   Θ(n log n)
aleatoria_s3     73           0     76        0.008  Medio   Θ(n log n)
aleatoria_s4     81           0     83        0.009  Medio        Θ(n²)
aleatoria_s5     62           0     64        0.007  Medio   Θ(n log n)

Cómo se lee esto (esta tabla es ORO porque muestra exactamente dónde insertion brilla):

1. ordenada → Mejor + Θ(n): 14 comparaciones, n−1 exactas. El recorrido lineal de libro: cada elemento compara con su vecino izquierdo y para.
2. casi_ordenada → Mejor + Θ(n log n): 31 comparaciones, solo 17 más que el caso óptimo. Aquí está la magia de insertion: sigue casi en el mejor caso aunque la lista tenga elementos descolocados. Por eso Timsort lo usa dentro.
3. Listas aleatorias → Medio: entre 62 y 81 comparaciones, alrededor de la mitad del peor caso. Es el comportamiento esperable estadísticamente.
4. inversa → Peor + Θ(n²): 105 comparaciones exactas (n(n-1)/2 para n=15). Cada elemento tiene que viajar hasta el principio.
5. Insertion NUNCA hace intercambios (columna Interc. = 0 siempre). Es porque está implementado con desplazamientos (shifts): mueve elementos a la derecha sin hacer swaps explícitos.

Compara con bubble sobre la lista casi_ordenada:

Algoritmo	Comparaciones	Tiempo
Insertion	31	0,004 ms
Bubble	95	0,008 ms

Insertion hace un tercio del trabajo sobre la misma lista. Por eso es muy superior cuando la lista está parcialmente ordenada, que es el caso real más frecuente en producción.

¿Y el escalado a n grande? Sobre aleatoria_s1:

n	Comparaciones	Tiempo
100	2.597	0,2 ms
1.000	249.438	23 ms
10.000	24.803.775	2.304 ms (2,3 s)

Crece como Θ(n²) sobre listas aleatorias. Pero sigue siendo más rápido que bubble a la misma escala (bubble en n=10.000 = 5,4 s) porque hace menos trabajo por iteración.

Reproducirlo sin instalar nada

sortlab vive privado en el Python profesional: medir, optimizar y escalar (con la implementación completa explicada y el porqué de cada número). Si quieres reproducirlo sin la librería, esta es la versión instrumentada que copia y pega:

def insertion_medido(lista_original: list[int]) -> dict:
    arr = list(lista_original)
    comparaciones = 0
    escrituras = 0
    for i in range(1, len(arr)):
        actual = arr[i]
        j = i - 1
        while j >= 0:
            comparaciones += 1
            if arr[j] <= actual:
                break
            arr[j + 1] = arr[j]
            escrituras += 1
            j -= 1
        arr[j + 1] = actual
        escrituras += 1
    return {"ordenada": arr, "comparaciones": comparaciones, "escrituras": escrituras}


listas = {
    "ordenada":         list(range(1, 16)),
    "inversa":          list(range(15, 0, -1)),
    "casi_ordenada":    [1, 11, 3, 4, 5, 6, 7, 8, 9, 10, 2, 12, 13, 14, 15],
    "muy_desordenada":  [1, 15, 2, 14, 3, 13, 4, 12, 5, 11, 6, 10, 7, 9, 8],
    "duplicados":       [1, 1, 3, 2, 2, 2, 1, 5, 1, 5, 4, 1, 1, 1, 2],
}
for nombre, lista in listas.items():
    r = insertion_medido(lista)
    print(f"{nombre:<16}  comp={r['comparaciones']:>3}  esc={r['escrituras']:>3}")

Las salidas coinciden con las filas correspondientes de la tabla.

Mitos que circulan sobre insertion sort

• “Es solo un algoritmo de juguete.” Falso. Es un componente real de Timsort (Python, JS, Java objetos) e Introsort (C++). Se usa todos los días, aunque no lo veas.
• “Bubble e insertion son básicamente lo mismo.” Mismo Big-O, pero insertion es claramente superior: hace menos trabajo en el caso medio y aprovecha mejor las listas casi ordenadas.
• “Si la lista es pequeña da igual cuál uses.” Para listas muy pequeñas (n<32) insertion es literalmente la mejor opción — supera a quicksort y merge por el overhead de éstos. Por eso los híbridos modernos cambian a insertion ahí.

¿Y en la stdlib de Python?

No directamente, pero sí indirectamente. Cuando llamas a list.sort() o sorted(), Python ejecuta Timsort, que internamente usa insertion sort para los tramos de menos de 32 elementos. Es decir: estás corriendo insertion sort sin saberlo cada vez que ordenas una lista corta.

Trivia algorítmica

Insertion sort es uno de los pocos algoritmos del manual que siguen vivos en código de producción real. El comentario en CPython Objects/listobject.c —el archivo C donde está implementado Timsort— menciona explícitamente que insertion sort se usa para “small arrays” en la fusión.

Cuándo usar insertion (que es a menudo)

Sí:

• Listas pequeñas (típicamente n ≤ 32). Su overhead es bajísimo, y bate a quicksort/merge para tamaños pequeños. Por eso los híbridos como Timsort y Introsort lo usan por dentro para tramos cortos.
• Listas que ya están casi ordenadas. Aquí su O(n) en el mejor caso lo convierte en la mejor opción posible.
• Inserción incremental. Si vas añadiendo elementos a una lista que mantienes ordenada, insertion sort encaja literalmente con el caso de uso.

No:

• Listas grandes desordenadas. El O(n²) lo entierra a partir de unos miles de elementos.
• Cuando ya tienes sorted() disponible. Python list.sort() es Timsort, que es más rápido en general y, además, usa insertion por dentro para los tramos pequeños.

Comparativa rápida

Dónde encaja insertion dentro del clúster:

Algoritmo	Mejor	Peor	Memoria	Estable	Ventaja
Bubble	Ω(n)	O(n²)	O(1)	Sí	Conceptualmente trivial
Insertion	Ω(n)	O(n²)	O(1)	Sí	El rey de las listas pequeñas o casi ordenadas
Selection	Ω(n²)	O(n²)	O(1)	No	Mínimo número de escrituras
Quicksort	Ω(n log n)	O(n²)	O(log n)	No	Súper rápido en la práctica
Merge sort	Ω(n log n)	O(n log n)	O(n)	Sí	Garantiza O(n log n) siempre

Y aquí viene el matiz interesante: insertion sort no es del todo “viejo y muerto”. Sigue corriendo dentro de los algoritmos modernos. Cuando Timsort detecta un tramo de menos de 32 elementos, se pasa a insertion. C++ Introsort lo usa cuando la recursión llega a tramos pequeños. Es un componente, no un competidor.

FAQ rápida

¿Por qué Python usa Timsort y no insertion directamente?
Porque insertion sort es O(n²) sobre listas grandes y desordenadas, y eso es inviable. Timsort lo usa SOLO para los tramos pequeños donde insertion gana, y combina con merge para todo lo demás.

¿Insertion sort es recursivo?
La versión clásica es iterativa. Existe una versión recursiva pedagógica, pero no aporta nada en la práctica.

¿Es estable insertion sort?
Sí. Los elementos iguales nunca se intercambian, así que mantienen su orden original.

¿Cuándo “insertion sort por intercambios” es preferible a la versión con shifts?
Casi nunca, salvo para visualizarlo (animación) o para ejercicios donde el enunciado pide explícitamente swap-based. La versión con shifts hace la mitad de operaciones.

¿Insertion sort es mejor que bubble?
En casi cualquier escenario, sí. Ambos son O(n²) en el peor caso, pero insertion hace menos trabajo en el caso medio y se beneficia más de listas casi ordenadas. Si dudas entre bubble e insertion, elige insertion.

En resumen

Insertion sort es uno de los pocos algoritmos O(n²) que sigue siendo útil en producción — pero no como algoritmo principal, sino como subrutina dentro de algoritmos modernos (Timsort, Introsort). Su don es brillar en listas pequeñas o casi ordenadas, justo el caso en el que los O(n log n) “buenos” pierden por overhead. Conocerlo bien es entender por qué los híbridos modernos lo siguen incluyendo.

Si quieres aprender a medir tu código de verdad y a elegir la estructura correcta para cada problema, ese es el camino del curso de El Pythonista.