Este es uno de los métodos más sencillos. Consta de tomar uno por uno los elementos de un arreglo y recorrerlo hacia su posición con respecto a los anteriormente ordenados. Así empieza con el segundo elemento y lo ordena con respecto al primero. Luego sigue con el tercero y lo coloca en su posición ordenada con respecto a los dos anteriores, así sucesivamente hasta recorrer todas las posiciones del arreglo. Este es el algoritmo:
Procedimiento Insertion Sort
Este procedimiento recibe el arreglo de datos a ordenar a[] y altera las posiciones de sus elementos hasta dejarlos ordenados de menor a mayor. N representa el número de elementos que contiene a[].
paso 1: [Para cada pos. del arreglo] For i <- 2 to N do
paso 2: [Inicializa v y j] v <- a[i]
j <- i.
paso 3: [Compara v con los anteriores] While a[j-1] > v AND j>1do
paso 4: [Recorre los datos mayores] Set a[j] <- a[j-1],
paso 5: [Decrementa j] setj <- j-1.
paso 5: [Inserta v en su posición] Set a[j] <- v.
paso 6: [Fin] End.
Ejemplo:
Si el arreglo a ordenar es a = [‘a’,‘s’,‘o’,‘r’,‘t’,‘i’,‘n’,‘g’,‘e’,‘x’,‘a’,‘m’,‘p’,‘l’,‘e’],
el algoritmo va a recorrer el arreglo de izquierda a derecha. Primero toma el segundo dato ‘s’ y lo asigna a v, i toma el valor de la posición actual de v.
Luego compara esta ‘s’ con lo que hay en la posición j-1, es decir, con ‘a’. Debido a que ‘s’ no es menor que ‘a’ no sucede nada y avanza i.
Ahora v toma el valor ‘o’ y lo compara con ‘s’, como es menor recorre a la ‘s’ a la posición de la ‘o’; decrementa j, la cual ahora tiene la posición en dónde estaba la ‘s’; compara a ‘o’ con a[j-1] , es decir, con ‘a’. Como no es menor que la ‘a’ sale del for y pone la ‘o’ en la posición a[j]. El resultado hasta este punto es el arreglo siguiente: a = [‘a’,‘o’,‘s’,‘r’,…]
Así se continúa y el resultado final es el arreglo ordenado :
a = [‘a’,‘a’,‘e’,‘e’,‘g’,‘i’,‘l’,‘m’,‘n’,‘o’,‘p’,‘r’,‘s’,‘t’,‘x’]
