Cómo funciona
Como cuando ordenas cartas en la mano. La parte izquierda del array está siempre
ordenada entre sí, aunque todavía no es definitiva: una carta posterior puede
caer en medio. En cada paso se toma la siguiente carta, la clave, y se busca su sitio
en esa parte, de derecha a izquierda.
Al levantar la clave queda un hueco. Cada carta mayor que la clave se
desplaza un puesto a la derecha, ocupando el hueco, que así se mueve hacia la izquierda.
Cuando aparece una carta menor o igual (o se llega al principio), la clave cae en el hueco.
Insertar es desplazar, no intercambiar: un desplazamiento copia un valor una vez, mientras que un
intercambio necesita tres escrituras. Por eso, moviendo los mismos pares, Insertion Sort escribe mucho
menos que Bubble Sort.
Paso a paso con [5, 3, 8, 1]
- 01i = 1, clave 3: 5 > 3, el 5 se desplaza. No quedan cartas a la izquierda: el 3 va a la posición 0 →
[3, 5, 8, 1]. 1 comparación, 1 desplazamiento.
- 02i = 2, clave 8: 5 ≤ 8, el 8 se queda donde estaba →
[3, 5, 8, 1]. 1 comparación, ningún desplazamiento.
- 03i = 3, clave 1: 8 > 1, 5 > 1 y 3 > 1: tres desplazamientos y el 1 llega al principio →
[1, 3, 5, 8]. 3 comparaciones.
- ΣTotal: 3 inserciones, 5 comparaciones y 4 desplazamientos. Bubble Sort, con el mismo array, hace 6 comparaciones y 4 intercambios: mueven los mismos 4 pares desordenados, pero 4 intercambios son 12 escrituras, y 4 desplazamientos más 3 inserciones, solo 7.
Cuándo se usa
Con datos casi ordenados cada clave se detiene enseguida y el coste se acerca a O(n).
Por eso muchas implementaciones reales de algoritmos rápidos, como Timsort o introsort, ordenan los
trozos pequeños con Insertion Sort.
Complejidad
- Mejor caso
- O(n)
- Caso promedio
- O(n²)
- Peor caso
- O(n²)
- Espacio extra
- O(1)
- Estable
- Sí
- In situ
- Sí