Algoritmos de Ordenação
Gabarito: letra D. O algoritmo Merge sort é implementado pelo paradigma de divisão e conquista, no qual o problema é recursivamente dividido em subproblemas menores até que sejam resolvidos e combinados. Essa é a definição clássica do Merge sort. As demais alternativas contêm afirmações incorretas sobre estabilidade do Radix sort, complexidade do Bubble sort, estrutura do Heapsort e eficiência do Insertion sort.
Alternativa A — ❌ Incorreta
Afirma que o Radix sort é um algoritmo de ordenação instável. Na verdade, o Radix sort pode ser implementado de forma estável (e normalmente o é quando se utiliza um sub-algoritmo estável como o Counting sort). A maioria das implementações convencionais do Radix sort é estável, portanto a afirmativa é falsa.
Alternativa B — ❌ Incorreta
A complexidade do Bubble sort é de ordem quadrática, O(n²), e não logarítmica. A complexidade logarítmica (O(log n)) é típica de algoritmos como a busca binária, não de ordenação por troca simples.
Alternativa C — ❌ Incorreta
O Heapsort utiliza uma árvore binária (heap binário), não ternária. O heap é uma árvore binária completa que satisfaz a propriedade de heap (max-heap ou min-heap). Uma árvore ternária teria até três filhos por nó, o que não corresponde à estrutura do Heapsort.
Alternativa D — ✅ Correta ⟵ GABARITO
O Merge sort é um exemplo clássico do paradigma divisão e conquista. Ele divide recursivamente a lista em duas metades, ordena cada metade e depois combina (merge) as metades ordenadas. Essa descrição corresponde exatamente ao que a alternativa afirma.
Alternativa E — ❌ Incorreta
O Insertion sort tem complexidade O(n²) no pior caso, enquanto o Quick sort tem complexidade média O(n log n). Para grandes entradas, o Quick sort é muito mais eficiente. O Insertion sort é vantajoso apenas para pequenas entradas ou dados quase ordenados.
Gabarito: letra D.