Ordenación por Inserción

La ordenación por Inserción aunque sigue siendo siendo del tipo O(n2), trabaja en una manera ligeramente diferente. Siempre mantiene una sublista ordenada en la posición más baja de la lista. Cada nuevo elemento es entonces “insertado” de regreso en la sublista previa tal que la sublista ordenada contiene un elemento más. En el siguiente ejemplo los elementos sombreados representan las sublistas ordenadas que el algoritmo genera en cada pasada.