Algoritmos de ordenação: recursão e iteração
Gabarito: letra A (Merge Sort). O Merge Sort é um algoritmo de ordenação que pode ser implementado tanto de forma recursiva (abordagem top-down, dividindo o problema em subproblemas menores) quanto de forma iterativa (abordagem bottom-up, combinando sublistas ordenadas de forma incremental). Essa dualidade o torna a alternativa correta.
A questão cobra o conhecimento de que, dentre os algoritmos listados, o Merge Sort é o que mais claramente admite ambas as técnicas. O Quick Sort, embora também possa ser implementado iterativamente, é tradicionalmente apresentado com recursão, e suas versões iterativas são menos difundidas em livros-texto. Já Insert Sort, Bucket Sort e Selection Sort são essencialmente iterativos.
Alternativa A — ✅ Correta ⟵ GABARITO
O Merge Sort é o exemplo clássico: sua versão recursiva (dividir para conquistar) e sua versão iterativa (bottom-up) são ambas amplamente estudadas. Ele utiliza recursão para dividir o array em subarrays menores e iteração (ou recursão) para intercalar as partes ordenadas.
Alternativa B — ❌ Incorreta
Insert Sort (ordenação por inserção) é um algoritmo iterativo, não recursivo. Ele constrói a sequência ordenada inserindo um elemento por vez na posição correta.
Alternativa C — ❌ Incorreta
Bucket Sort (ordenação por balde) é um algoritmo distributivo, baseado em iteração sobre os baldes e sobre os elementos dentro deles. Não utiliza recursão.
Alternativa D — ❌ Incorreta
Selection Sort (ordenação por seleção) é puramente iterativo: a cada passo, seleciona o menor elemento restante e o coloca na posição correta.
Alternativa E — ❌ Incorreta
Embora o Quick Sort seja tipicamente recursivo, ele também admite implementação iterativa (usando pilha explícita). Contudo, a banca considerou o Merge Sort como o que “usa tanto técnicas recursivas como não recursivas”, provavelmente por ser o mais emblemático nesse aspecto. Além disso, a questão pode ter sido projetada para destacar o Merge Sort como resposta correta.
Gabarito: letra A (Merge Sort).