Comparações do merge sort: pior caso e caso médio

Ela informa o total exato do pior caso, o valor esperado para uma ordem aleatória uniforme, a quantidade de níveis recursivos e n vezes o logaritmo de n na base 2 como referência. Assim, você consegue visualizar o crescimento linearítmico e compará-lo ao comportamento quadrático.

O que a calculadora contabiliza

O cálculo considera comparações de ordenação entre elementos durante a intercalação, operação central da análise tradicional do merge sort. Não entram verificações de índice, atribuições, gravações em vetores temporários, chamadas recursivas, alocações nem o trabalho interno de um comparador personalizado. Um único elemento não exige comparação. Em entradas maiores, o algoritmo divide a faixa, ordena as duas partes e compara repetidamente os primeiros elementos ainda não consumidos. Intercalar grupos de a e b elementos exige no máximo a mais b menos uma comparações, pois o último elemento restante pode ser copiado diretamente. O pior caso combina essa regra em toda a árvore real de divisões, inclusive quando n não é potência de dois. Portanto, use n_log2_n como escala e os campos de comparações como estimativas operacionais.

Como o pior caso e a média são obtidos

A fórmula exata do pior caso é n multiplicado pelo teto do logaritmo de n na base 2, menos dois elevado a esse teto, mais um. Ela representa um merge sort binário padrão, com subvetores divididos da forma mais equilibrada possível. A média é uma esperança sobre permutações uniformemente aleatórias de chaves distintas. Em cada intercalação de trechos com a e b elementos, o valor esperado é a mais b, menos a dividido por b mais um, menos b dividido por a mais um. A calculadora soma esse custo recursivamente na mesma árvore equilibrada e arredonda apenas o resultado exibido para seis casas decimais. A esperança pode ser fracionária, embora cada execução faça um número inteiro de comparações. Chaves repetidas, outros critérios de desempate, sequências naturais e limites para insertion sort podem mudar o total observado.

Como interpretar o resultado linearítmico

O valor n_log2_n representa a escala linearítmica característica. Cada nível adicional de intercalação processa todos os n elementos, enquanto a quantidade de níveis cresce apenas de modo logarítmico. Os dois campos de proporção dividem as estimativas por n vezes o logaritmo de n na base 2 e mostram a proximidade dos totais concretos dessa referência quando n é maior que um. Eles são descritivos, não provas de complexidade nem benchmarks de hardware. Tráfego de memória, alocação, custo do comparador, cache e ambiente de execução podem dominar o tempo real. Experimente tamanhos logo abaixo e acima de potências de dois. Nessas fronteiras, a profundidade recursiva muda e fica claro por que a notação O grande descarta constantes e termos menores sem torná-los irrelevantes para uma entrada específica.