Sobre o Método de Ordenação Merge Sort, é CORRETO afirmar que:

A = Divisão e Conquista

B = Divisão e Conquista

C = Mais eficiente no MÉDIO e PIOR CASO, e serve para muitos e poucos dados

D = BUBBLE é mais eficiente que o MERGE no MELHOR CASO

GABARITO E

O Bubble Sort, no melhor caso, é mais eficiente que o Merge Sort, pois a complexidade do primeiro é O(n) e do segundo é O(n log n).

Na ordem de precedência das funções na notação assintótica, temos (do melhor para o pior):

1. O(1);
2. O(log n);
3. O(n) <- melhor caso do Bubble Sort
4. O(n log n) <- Merge Sort
5. O(nˆ2);
6. O(2ˆn);
7. O(n!);
8. O(nˆn).

Gabarito: E

A alternativa correta é a E: "O Merge Sort, ou Ordenação por Mistura, é um algoritmo de ordenação que usa a estratégia dividir-para-conquistar".

Vamos entender por que a alternativa E está correta e também analisar por que as outras estão incorretas.

Alternativa E: O Merge Sort é um algoritmo clássico que utiliza a estratégia de dividir-para-conquistar. Isso significa que ele divide repetidamente o problema em subproblemas menores e mais manejáveis, resolve esses subproblemas de forma recursiva e, finalmente, combina as soluções para formar a solução do problema original. Este método é eficiente e tem uma complexidade de tempo de O(n log n) em todos os casos, sejam eles piores, melhores ou médios.

Alternativa A: Está incorreta porque o Merge Sort não é um algoritmo de ordenação por inserção. Um exemplo de algoritmo de ordenação por inserção é o Insertion Sort, que insere cada elemento na posição correta em uma lista já ordenada.

Alternativa B: Também está incorreta porque o Merge Sort não é um algoritmo de ordenação por seleção. Um exemplo de algoritmo de ordenação por seleção é o Selection Sort, que seleciona repetidamente o menor (ou maior) elemento da lista e o coloca na posição correta.

Alternativa C: Está incorreta porque o Merge Sort é mais eficiente que o Bubble Sort não apenas quando há poucos dados a serem ordenados, mas em praticamente todos os casos. A complexidade do Bubble Sort é O(n²), que é significativamente pior que a do Merge Sort.

Alternativa D: Está parcialmente correta, mas falta especificidade. É verdade que o Merge Sort é geralmente mais eficiente que o Bubble Sort em todos os casos, mas a alternativa não especifica o motivo, que é a diferença na complexidade de tempo.

Em resumo, a alternativa E é a mais precisa e correta, pois descreve a estratégia fundamental do Merge Sort, a dividir-para-conquistar, que é a chave para seu desempenho eficiente.