Insertion sort (ordenamiento por inserción): cómo funciona, código y complejidad

La idea en palabras sencillas

Considera el primer elemento como una lista ordenada de longitud uno. Toma el segundo elemento e insértalo antes o después del primero. Toma el tercero e insértalo en el lugar correcto entre los dos primeros. Continúa hasta que todos los elementos hayan sido insertados.

Para insertar, aparta el nuevo elemento (llámalo key) y recorre hacia la izquierda la parte ordenada. Cada elemento mayor que key se mueve una posición a la derecha. Cuando llegues a un elemento que no sea mayor, o al inicio de la lista, coloca key en el hueco vacío.

Ejemplo resuelto, paso a paso

Ordena [12, 11, 13, 5, 6]. La parte anterior a la barra está ordenada (pero aún no es definitiva).

Fíjate en el paso 2: un elemento que ya está en su sitio cuesta una sola comparación. Por eso insertion sort es rápido con entradas casi ordenadas.

Implementación en Python

def insertion_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and items[j] > key:   # strict >, keeps it stable
            items[j + 1] = items[j]        # shift right
            j -= 1
        items[j + 1] = key                 # drop into the gap
    return items
print(insertion_sort([12, 11, 13, 5, 6]))   # [5, 6, 11, 12, 13]
print(insertion_sort([1, 2, 3, 4]))         # [1, 2, 3, 4], 3 comparisons

Desplazar en lugar de intercambiar escribe cada elemento movido una sola vez, lo que supone aproximadamente la mitad del trabajo de la versión basada en intercambios. También puedes encontrar el punto de inserción con búsqueda binaria, como abajo. Esto reduce las comparaciones a O(n log n) en total, pero los desplazamientos siguen siendo O(n²), así que el tiempo global sigue siendo O(n²).

from bisect import insort_right
def binary_insertion_sort(items):
    result = []
    for x in items:
        insort_right(result, x)   # stable: equal items go after
    return result
print(binary_insertion_sort([3, 1, 2, 1]))   # [1, 1, 2, 3]

Complejidad temporal y espacial

Con más precisión, el tiempo de ejecución es O(n + I), donde I es el número de inversiones (pares desordenados). Si cada elemento está como máximo a k posiciones de su lugar final, I es como mucho n · k, así que insertion sort es O(n · k): muy rápido cuando k es pequeño.

Cómo se compara insertion sort con otros ordenamientos

Insertion sort es estable porque un elemento solo se mueve a la izquierda por encima de elementos estrictamente mayores. También es online: puede ordenar los datos a medida que llegan, manteniendo un prefijo ordenado en todo momento. Con listas cortas, su baja sobrecarga supera a los algoritmos O(n log n), así que Timsort (usado por Python y por Java para objetos) ordena las secuencias cortas con insertion sort binario, y muchas implementaciones de quicksort cambian a insertion sort por debajo de un tamaño pequeño.

Variantes y errores comunes

• Insertion sort binario: búsqueda binaria de la posición y luego desplazamiento. Menos comparaciones, lo que ayuda cuando comparar es costoso.
• Shell sort: aplica insertion sort a elementos separados por un hueco y luego reduce el hueco hasta 1. Mueve rápidamente los elementos lejanos y es mucho más rápido que insertion sort simple en arreglos grandes.
• Insertion sort en listas enlazadas: no hace falta desplazar, pero encontrar la posición sigue siendo un recorrido lineal.

Cuándo usar insertion sort

Úsalo para arreglos pequeños (decenas de elementos), para datos casi ordenados, como una lista que se ordenó y a la que luego se añadieron unos pocos elementos, y cuando necesites un ordenamiento estable, simple e in situ. Para datos aleatorios grandes, usa un ordenamiento O(n log n); en Python eso significa sorted() o list.sort(), que ya aplican insertion sort internamente a las secuencias cortas.

Las preguntas de entrevista suelen pedir la traza, el mejor y el peor caso, por qué es estable o por qué supera a los algoritmos O(n log n) con entradas pequeñas y casi ordenadas.