Algoritmos de ordenação baseados em dividir para conquistar.
  1. 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:
1. Se o vetor tem tamanho 1 (ou 0), está ordenado e retorna em tempo \Theta(1).
2. 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 n em tempo \Theta(n), pois percorre cada elemento exatamente uma vez.

Passo 3

Modelamos o tempo de execução T(n)\) por uma recorrência: \[T(n) \;=\; \begin{cases} \Theta(1), & \text{se }n\le1,\\\\ 2\,T\bigl(\tfrac n2\bigr)+\Theta(n), & \text{se }n>1. \end{cases}
Aqui o termo 2\,T(n/2)\] vem das duas chamadas recursivas, e \(\Theta(n) é o custo da fusão.

Passo 4

Aplicando o Teorema Mestre (caso a=2, b=2, f(n)=\Theta(n)), temos
T(n)=\Theta(n\log n).
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 n 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 \Theta(n) de custo, independentemente da disposição inicial.

Resposta

Não. O merge sort sempre executa em tempo \Theta(n\log n) para melhor, médio e pior caso, pois sua recorrência
T(n)=2\,T\bigl(\tfrac n2\bigr)+\Theta(n)
produz \Theta(n\log n) e o custo de fusão \Theta(n) não diminui mesmo que o vetor já esteja ordenado.

Exercícios relacionados