Time and Space Complexity

Complexidade de Tempo:

• Melhor Caso: O(n)
  • Quando o array já está ordenado, o Insertion Sort faz apenas uma passagem para confirmar a ordem de ordenação.
• Caso Médio e Pior Caso: O(n²)
  • Nos casos médio e pior, leva tempo quadrático porque, para cada elemento, podemos precisar comparar e deslocar por toda a parte ordenada.

Complexidade de Espaço:

• O(1)
  • O Insertion Sort é um algoritmo "in-place", o que significa que não requer memória adicional proporcional ao tamanho da entrada.
  • O espaço usado para a ordenação permanece constante, independentemente do tamanho da entrada.

Resumo:

• O Insertion Sort é eficiente para pequenos conjuntos de dados ou arrays quase ordenados.
• É menos adequado para grandes conjuntos de dados devido à sua complexidade de tempo quadrática.
• A complexidade de espaço é constante, tornando-o eficiente em termos de memória para qualquer tamanho de entrada.