Ordenamiento por inserción - Insertion sort

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.
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). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

El algoritmo en pseudocódigo (con listas que empiezan por 0) debería ser como el siguiente:

algoritmo insertSort( A : lista de elementos ordenables )
para i=1 hasta longitud(A) hacer
     index=A[i]
     j=i-1
     mientras j>=0 y A[j]>index hacer
          A[j + 1] = A[j]
          j = j - 1
     fin mientras
     A[j + 1] = index
fin para
fin algoritmo

Ahora una implementacion en C:

typedef int element;

void insertionsort(element *a, int n){

int i,j;
element t;
for(i=1;i=0 && a[j]>t;j--) {
  a[j+1] = a[j];
 }
 a[j+1] = t;
}
return;
}

La funcion insertionsort toma un puntero a la lista de elementos, y un entero que representa la cantidad de elementos a ordenar.