Algoritmos de Ordenação
Gabarito: letra D. O Merge Sort utiliza a estratégia de divisão e conquista, quebrando o problema em subproblemas menores, resolvendo-os recursivamente e combinando as soluções. As demais alternativas contêm erros conceituais clássicos sobre complexidade, estabilidade e classificação.
Alternativa A — ❌ Incorreta
Afirma que o Bubble Sort tem complexidade O(n log n). Na verdade, o Bubble Sort tem complexidade O(n²) no pior caso e no caso médio, e apenas O(n) no melhor caso (vetor já ordenado). A confusão comum é com algoritmos eficientes como Merge Sort ou Quick Sort, que têm O(n log n).
Alternativa B — ❌ Incorreta
Afirma que o Quick Sort é estável. O Quick Sort não é estável por padrão, pois a partição pode trocar a ordem relativa de elementos iguais. Algoritmos estáveis comuns são Insertion Sort, Merge Sort e Bubble Sort (quando implementados adequadamente).
Alternativa C — ❌ Incorreta
Afirma que o Insertion Sort é menos eficiente que o Selection Sort. Na prática, o Insertion Sort costuma ser mais eficiente que o Selection Sort para conjuntos pequenos ou quase ordenados, embora ambos tenham complexidade O(n²). A afirmação inversa é verdadeira apenas em cenários muito específicos, mas como regra geral está errada.
Alternativa D — ✅ Correta ⟵ GABARITO
O Merge Sort é um exemplo clássico de algoritmo de divisão e conquista: divide o vetor ao meio recursivamente até ter subvetores de um elemento, depois os combina de forma ordenada. Essa estratégia reduz a complexidade para O(n log n) no pior caso.
Alternativa E — ❌ Incorreta
Afirma que o Radix Sort é um algoritmo de comparação. Na verdade, o Radix Sort é um algoritmo de ordenação não comparativa, que ordena números processando dígitos individuais. Ele não compara elementos diretamente, mas sim agrupa pelos dígitos.
Gabarito: letra D.