Muitos dos algoritmos conhecidos são recursivos em sua estrutura, ou seja, para resolver um determinado problema, eles chamam recursivamente a si próprios (uma ou mais vezes) e lidam com os subproblemas relacionados. Esses algoritmos normalmente seguem uma abordagem de dividir e conquistar: eles dividem e problema em várias instâncias semelhantes ao problema original, mas menores em tamanho, resolvem as instâncias recursivamente e. em seguida, as soluções são combinadas para construir uma solução para o problema.

O algoritmo Merge Sort segue de perto o paradigma dividir e conquistar. Ele é um importante algoritmo para ordenação de dados em memória principal. Como ele é baseado em uma estratégia de divisão e conquista, uma de suas principais operações está relacionada com a mesclagem dos subvetores [instâncias de menor tamanho) ordenados.

Em um curso de Sistemas de Informação, algumas aulas foram dedicadas à análise dos algoritmos de ordenação mais tradicionais. Em uma dessas aulas, o algoritmo Merge Sort foi estudado e o professor lançou um desafio para os alunos. Foi pedido para que eles julgassem algumas afirmações sobre o processo de ordenação realizado pelo algoritmo sobre um vetor composto dos seguintes elementos: 38, 27, 43, 3, 9, 82. 10.

Considerando o desafio proposto pelo professor, avalie as afirmações a seguir.

I - professor afirmou que o numero de chamadas recursivas até que todos os subvetores de tamanho 1 sejam gerados é o mesmo para as duas metades do vetor original.

II - De acordo com o professor, para a construção do vetor ordenado, o procedimento de mesclagem precisa ser invocado seis vezes.

III - Outra afirmação feita pelo professor foI a de que apenas um subvetor gerado a partir do processo de divisão tem tamanho 1

IV. Finalmente, o professor disse que em todos os processos de mesclagem há troca de posição entre chaves

Está correto apenas o que se afirma em

A - I e IV.

B - I e ll.

C - II, III e IV.

D II e III.

E I, III e IV.