El Ordenamiento por Inserción construye la lista ordenada un elemento a la vez, como cuando ordenas cartas en tu mano: tomas la siguiente carta y la insertas en la posición correcta desplazando las mayores hacia la derecha.

Es el algoritmo de referencia para datos casi ordenados y para ordenamiento en línea (datos que llegan uno por uno). En la práctica, supera a Bubble Sort y Selection Sort en la mayoría de escenarios.

Cómo Funciona

1. Comienza desde el índice 1 (el segundo elemento).
2. Guarda el valor actual en una variable key.
3. Compara key con los elementos a su izquierda (ya ordenados).
4. Desplaza todos los elementos mayores que key una posición a la derecha.
5. Inserta key en la posición vacía resultante.
6. Repite para cada posición hasta el final del arreglo.

Idea Clave

La región [0, i-1] siempre está ordenada. Insertar el elemento i en esa región es como buscar en una lista ordenada: puedes usar búsqueda binaria para encontrar la posición de inserción en O(log n), aunque el desplazamiento sigue siendo O(n) en el peor caso.

La adaptividad es su superpoder: si el arreglo está casi ordenado, cada elemento solo se desplaza unas pocas posiciones, dando O(n + d) donde d es el número de inversiones.

Ejemplo Trabajado

Ordena [5, 3, 8, 1, 2] con Ordenamiento por Inserción:

i=1 (key=3):

• “Compara 3 con 5: 5 > 3, desplaza 5 → [5, 5, 8, 1, 2]”
• Inserta 3 en posición 0 → [3, 5, 8, 1, 2]

i=2 (key=8):

• “Compara 8 con 5: 5 ≤ 8, no desplaza → [3, 5, 8, 1, 2]”

i=3 (key=1):

• “Compara 1 con 8: 8 > 1, desplaza 8 → [3, 5, 8, 8, 2]”
• “Compara 1 con 5: 5 > 1, desplaza 5 → [3, 5, 5, 8, 2]”
• “Compara 1 con 3: 3 > 1, desplaza 3 → [3, 3, 5, 8, 2]”
• Inserta 1 en posición 0 → [1, 3, 5, 8, 2]

i=4 (key=2):

• Desplaza 8, 5, 3 → [1, 3, 3, 5, 8]
• Inserta 2 en posición 1 → [1, 2, 3, 5, 8]

Resultado: [1, 2, 3, 5, 8]. Observa el visualizador colorear la región ordenada y mostrar cada desplazamiento.

Casos Extremos y Trampas

• Datos casi ordenados — rendimiento cercano a O(n). Insertion Sort brilla aquí.
• Datos inversos — peor caso O(n²), cada elemento debe desplazarse hasta el frente.
• “Estabilidad — Insertion Sort es estable: solo intercambia en >, nunca en >=, preservando el orden de elementos iguales.”
• Arreglos pequeños — para n < 20, Insertion Sort a menudo gana a algoritmos más complejos por su bajo overhead.

Comparación con Otros Ordenamientos

Aplicaciones

• Ordenamiento en línea — datos que llegan uno por uno (logs, streams)
• Arreglos pequeños — como base de Timsort para fragmentos pequeños
• Datos casi ordenados — lists maintainedos con inserciones frecuentes
• Enseñanza — introduce el concepto de construcción incremental

Trayectoria de Práctica

1. Traza Insertion Sort en [4, 2, 7, 1, 3], mostrando el arreglo después de cada inserción.
2. Explica por qué Insertion Sort hace menos comparaciones que Bubble Sort en promedio.
3. Implementa una versión con búsqueda binaria para encontrar la posición de inserción.
4. Analiza el comportamiento cuando el arreglo ya está ordenado: ¿cuántas comparaciones y desplazamientos?
5. Compara Insertion Sort vs Selection Sort en términos de número de swaps.