Cómo funciona
Es Insertion Sort con saltos largos. Con un salto h, el array se reparte en h
subsecuencias intercaladas (posiciones 0, h, 2h…; 1, h + 1…) y cada una se ordena por inserción:
la clave se compara con el elemento que está h posiciones a su izquierda y los mayores
saltan h posiciones a la derecha.
El salto se reduce en cada ronda (aquí con la secuencia de Knuth: …, 40, 13, 4, 1). El último es
siempre h = 1, un Insertion Sort normal, pero sobre un array en el que cada número ya está cerca de su
sitio, así que los desplazamientos son cortos.
Paso a paso con [8, 5, 4, 7, 1, 3]
Con 6 elementos los saltos son h = 4 y h = 1.
- 01h = 4: clave 1, compara con el 8 de la posición 0: 8 > 1, el 8 salta a la posición 4 y el 1 cae en la 0. Clave 3: 5 > 3, el 5 salta a la 5 y el 3 cae en la 1 →
[1, 3, 4, 7, 8, 5]. 2 comparaciones, 2 desplazamientos.
- 02h = 1: Insertion Sort normal. Del 3 al 8 cada clave se queda en su sitio tras una comparación; el 5 desplaza al 8 y al 7 →
[1, 3, 4, 5, 7, 8]. 7 comparaciones, 2 desplazamientos.
- ΣTotal: 9 comparaciones y 4 desplazamientos. Insertion Sort, con el mismo array, haría 14 comparaciones y 12 desplazamientos: el 1 y el 3 tendrían que avanzar 4 posiciones cada uno, de una en una.
Por qué funciona
El punto débil de Insertion Sort son las tortugas: valores pequeños al final, que
avanzan un puesto por desplazamiento. Un salto largo las acerca al principio en pocas operaciones.
Además, un array h-ordenado sigue h-ordenado después de ordenarlo con un salto menor, así que el
trabajo de cada ronda no se pierde.
El precio es la estabilidad: un salto largo puede pasar un 5 por encima de otro 5. Y con datos casi
ordenados las rondas de saltos largos son trabajo extra: cada una compara casi n veces sin mover nada,
mientras que Insertion Sort ya habría terminado.
Complejidad
- Mejor caso
- O(n log n)
- Peor caso (Knuth)
- O(n^1,5)
- Espacio extra
- O(1)
- Estable
- No
- Saltos
- h = 3h + 1
- In situ
- Sí