Método de inserción.

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

                                   

Pseudicódigo

algoritmo insercion( A : array de n elementos indizados de 1 a n)
variables: enteros i,j, temporal
//estas son las pasadas, desde 2 hasta n
//en cada una intentaremos encontrar la posición
//relativa del elemento i entre los anteriores
para i desde 2 hasta n
j=i-1
//vamos "descendiendo" el elemento
//haciendo intercambios
mientras (j>=1) Y (A[j]>A[j+1]) hacer
//intercambio de la posicion j y la siguiente
temporal=A[j+1]
A[j+1]=A[j]
A[j]=temporal
j=j-1
fin mientras
fin para
fin algoritmo