Algoritmos de ordenação baseados em dividir para conquistar.
- O tempo do merge sort depende da ordem dos valores do vetor a ser ordenado? Explique detalhadamente sua resposta.
Passo 1
O enunciado pergunta se o tempo de execução do merge sort, um algoritmo de ordenação por dividir e conquistar, varia conforme a ordem inicial dos elementos no vetor. O conteúdo aqui é análise de complexidade de algoritmos recursivos e usaremos a recorrência do merge sort e o Teorema Mestre para verificação.
Passo 2
Descrevendo o funcionamento do merge sort:
. Se o vetor tem tamanho
(ou
), está ordenado e retorna em tempo
.
. Caso contrário, divide o vetor ao meio, recursivamente ordena cada metade e depois funde (merge) as duas metades ordenadas.
A fase de fusão junta duas sublistas de tamanhos somando em tempo
, pois percorre cada elemento exatamente uma vez.
A fase de fusão junta duas sublistas de tamanhos somando
Passo 3
Modelamos o tempo de execução
Aqui o termo
é o custo da fusão.
Passo 4
Aplicando o Teorema Mestre (caso
,
,
), temos
Isso vale para o melhor, pior e caso médio, pois a recorrência e o custo de fusão não mudam se o vetor já estiver ordenado, inversamente ordenado ou em ordem aleatória.
Passo 5
Argumento detalhado sobre a independência da ordem inicial:
- Na etapa de divisão não há comparações entre elementos, só índices.
- Na fusão, mesmo que todos os elementos de uma metade sejam menores do que os da outra, ainda assim o algoritmo precisa percorrer todos os
elementos para copiá-los na ordem certa. - Não existe “atalho” que reduza linearmente esse trabalho quando o vetor já está ordenado, portanto cada nível da recursão sempre soma
de custo, independentemente da disposição inicial.
Resposta
Não. O merge sort sempre executa em tempo
para melhor, médio e pior caso, pois sua recorrência
produz
e o custo de fusão
não diminui mesmo que o vetor já esteja ordenado.