Este algoritmo, como o próprio nome já diz, ordena através de inserções e é baseado em comparação. Sua maneira de ordenar é geralmente comparada com uma pessoa colocando cartas na ordem correta em um baralho. Muito eficiente para poucos elementos [Cormen, 2002].

Complexidade
Melhor Caso: Θ(n);
Caso Médio: Tende a ser Θ(n²);
Pior Caso: Θ(n²).


Testes
Analisaremos os gráficos a respeito do desempenho do Insertion-Sort começando pela entrada ordenada.

Insertion-Sort Entrada Ordenada (Tempo 0 a 10.000 segundos)

Podemos notar que para entradas ordenadas de diversos tamanhos o tempo deste algoritmo é linear. No próximo gráfico mostraremos esse mesmo teste com o eixo vertical (tempo) focado apenas no intervalo de 0 a 0,05 segundos para uma melhor visualização da variação dos tempos.

Insertion-Sort Entrada Ordenada Detalhado (Tempo 0 a 0,05 segundos)

Agora continuamos a observar o mesmo teste porém com melhor noção dos tempos e podemos perceber da mesma maneira que sua regressão linear ainda é bastante convincente mostrando que realmente o Insertion-Sort para entradas ordenadas é linear.

Insertion-Sort Entrada Inversamente Ordenada (Tempo 0 a 10.000 segundos)


Já para a entrada inversamente ordenado podemos perceber que o algortimo perde toda sua linearidade e se torna visivelmente quadrático o que torna seu uso para uma entrada deste tipo inaceitável.

Insertion-Sort Entrada Aleatória (Tempo 0 a 10.000 segundos)

Uma entrada aleatória torna o tempo do Insertion-Sort quadrático, que é exatamente o que foi dito sobre sua complexidade no caso médio tendendo a ser exponencial.

Não deixe de conferir a implementação desde algoritmo!