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.

Gráfico 1: 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.

Gráfico 2: 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.

Gráfico 3: 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.

Veja também:
Explicação Teórica!
Implementação em C/C++!