Este algoritmo segue o princípio da divisão e conquista e quando os arranjos possuem tamanho mínimo são intercalados recursivamente até que voltem a formar apenas uma arranjo com todos os elementos ordenados, para ocorrer essa ordenação o algoritmo se baseia em comparações. Uma desvatagem sua é a necessidade de espaço de memória adicional para se alocar o arranjo auxiliar.

Complexidade:
Melhor Caso: Θ(n lg n);
Caso Médio: Θ(n lg n);
Pior Caso: Θ(n lg n).


Testes
Agora analisaremos o Merge-Sort, esse algoritmo é ótimo pois ordena para qualquer entrada na melhor complexidade possível considerando algoritmos de ordenação baseados em comparação.

Merge-Sort Entrada Ordenada (Tempo 0 a 1 segundo)

Analisando este gráfico e sua aproximação logarítmica, podemos notar que seus comportamentos são muito próximos mas também fica desenhada quase uma reta mostrando que o n do n lg n influencia bastante no formato da curva.


Merge-Sort Entrada Inversamente Ordenada (Tempo 0 a 1 segundo)

Para uma entrada inversamente ordenada o comportamento do Merge é praticamente o mesmo que para uma entrada ordenada.


Merge-Sort Entrada Aletória (Tempo 0 a 1 segundo)

Já na entrada aleatória seu tempo aumenta um pouco porém o comportamento é o mesmo talvez tenham sido feitas algumas trocas a mais que levaram a esse pequeno crescimento de tempo. Como podemos ver através desses gráficos o Merge-Sort é muito estável quanto ao seu tempo de execução e por isso indicado para realizar ordenações onde o tipo da entrada é desconhecido, lembrando sempre da sua desvantagem de alocação de espaço de memória adicional.

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