Time and Space Complexity

Complexidade de Tempo:

• Melhor, Médio e Pior Caso: O(n log n)
  • O array é dividido ao meio cerca de log n vezes, e cada nível realiza O(n) de trabalho para intercalar (merge). O tempo de execução não depende da ordem de entrada.

Complexidade de Espaço:

• O(n)
  • Ao contrário das ordenações in-place, o Merge Sort constrói novos arrays durante a intercalação, portanto, precisa de memória extra proporcional ao tamanho da entrada.

Resumo:

• O Merge Sort é rápido e previsível: O(n log n) em todos os casos.
• Ele é estável, portanto, elementos iguais mantêm sua ordem.
• A desvantagem é a memória extra O(n) que ele utiliza para a intercalação.