La ordenación por inserción es considera como un algoritmo sencillo, este algoritmo tiene la característica de mantener ordenadas las regiones sin ordenar de la matriz. En cada iteración, el siguiente elemento sin ordenar se mueve hacia arriba a una apropiada posición en la región donde están ordenados. Es mucho menos eficiente en grandes listas, que los más algoritmos avanzados como quicksort. Pero tiene algunas ventajas:
-Fácil de implementar
-Eficiente en (bastante) pequeños conjuntos de datos
-Eficiente en conjuntos de datos que ya están ordenados sustancialmente
-Estable (no cambia el orden relativo de los elementos)
En términos abstractos, cada iteración de una ordenación por inserción elimina un elemento de la entrada de datos, insertándolo en la posición correcta en la lista ya ordenada, hasta que no haya elementos en la entrada. La elección del elemento a eliminar de la entrada es arbitraria.
A continuación el algoritmo por el método de inserción en java
void insertionSort (int[] A) {
int j;
for (int i = 1; i < A.length; i++) {
int a = A[i];
for (j = i - 1; j >=0 && A[j] > a; j--){
A[j + 1] = A[j];
}
A[j + 1] = a;
}
}
