Este algoritmo ordena los primeros dos elementos del vector, a continuación toma el tercer elemento y lo ordena en la posición correspondiente. Cuando termina de ubicar un elemento en su posición correcta, continúa con el siguiente elemento, hasta hacer este proceso con todos los elementos del vector.

Ejemplo:

Primeramente tenemos el vector desordenado.

Iteración 1:

Se ordenan los primeros dos elementos.

Iteración 2:

Se ordenan los elementos 3 y 4.

Se toma el tercer elemento 23 y se ordena entre el primer elemento y el segundo, recorriéndose el 45 a la tercera posición.

Iteración 3:

No hay cambio ya que el 67 es mayor al 45.

Iteración 4:

Se toma el número 21, y se mete en la posición correspondiente del vector, recorriendo los números mayores.

Y así tenemos el vector ordenado.

public static int[] ordenacionInsercion(int vec[]){
                final int N=vec.length;
                for(int i=1;i<N;i++){
                        int j=i;
                        while(j>0&&vec[j]<vec[j-1]){
                                int temp=vec[j];
                                vec[j]=vec[j-1];
                                vec[j-1]=temp;
                                j--;
                        }
                }
                return vec;
        }

public class Insercion {

        public static void main(String[] args) {
                int vec[]={45,17,23,67,21};
                System.out.println("Vector original");
                imprimirVector(vec);
                System.out.println("\n");
                vec=ordenacionInsercion(vec);
                imprimirVector(vec);
        }

        public static int[] ordenacionInsercion(int vec[]){
                final int N=vec.length;
                for(int i=1;i<N;i++){
                        int j=i;
                        while(j>0&&vec[j]<vec[j-1]){
                                int temp=vec[j];
                                vec[j]=vec[j-1];
                                vec[j-1]=temp;
                                j--;
                        }
                        System.out.print("iteracion: "+i+": ");imprimirVector(vec);System.out.println();
                }
                return vec;
        }
        
        public static void imprimirVector(int vec[]){
                for(int i=0;i<vec.length;i++){
                        System.out.print(vec[i]+" ");
                }
        }
}