MergeSort – Propriedades Fundamentais
Gabarito: letra B. O MergeSort é um algoritmo de ordenação estável, ou seja, mantém a ordem relativa de elementos iguais. Essa é uma característica bem conhecida do algoritmo, ao contrário do QuickSort (que não é estável na implementação típica). As demais alternativas contêm erros: o MergeSort tem complexidade O(n log n) no pior caso, igual ao QuickSort em média (A); a divisão nem sempre é exatamente igual (C); e ele requer espaço extra O(n), não é in-place (D).
Alternativa A — ❌ Incorreta
Afirma que o MergeSort tem complexidade de tempo média pior que o QuickSort. Na verdade, ambos possuem complexidade média O(n log n). O QuickSort tem pior caso O(n²), enquanto o MergeSort mantém O(n log n) em todos os casos. A afirmativa é falsa.
Alternativa B — ✅ Correta ⟵ GABARITO
O MergeSort é estável porque, durante a intercalação, elementos iguais são processados na ordem em que aparecem, preservando sua posição relativa. Essa é uma propriedade importante para ordenação de pares chave-valor.
Alternativa C — ❌ Incorreta
O MergeSort divide o array aproximadamente ao meio. Quando o número de elementos é ímpar, as partes diferem em tamanho (ex.: 7 elementos → partes de 4 e 3). Portanto, a divisão não é sempre em partes iguais.
Alternativa D — ❌ Incorreta
O MergeSort não é in-place. Ele requer espaço extra proporcional a n para armazenar os subarrays durante a intercalação (tipicamente O(n)). Algoritmos in-place, como Heapsort ou QuickSort, realizam a ordenação com pouca memória adicional constante.
Gabarito: letra B