O Merge Sort usa a estratégia de dividir para conquistar: divide o vetor ao meio repetidamente até sobrarem pedaços de um elemento e depois intercala (merge) esses pedaços em ordem, de dois em dois, até reconstruir o vetor inteiro ordenado.
Como o Merge Sort Funciona
- Divida o vetor em duas metades.
- Ordene cada metade recursivamente com o próprio Merge Sort.
- Intercale as duas metades: compare o primeiro de cada uma e copie o menor.
- Quando uma metade acabar, copie o restante da outra.
- Vetores de 1 elemento já estão ordenados (caso base da recursão).
Complexidade do Merge Sort
| Melhor caso | Caso médio | Pior caso | Memória extra | Estável? |
|---|---|---|---|---|
| O(n log n) | O(n log n) | O(n log n) | O(n) | Sim |
Quando usar
Quando é preciso garantir O(n log n) no pior caso e estabilidade, como ao ordenar registros por mais de um critério. Também é a base para ordenar dados que não cabem na memória (ordenação externa) e listas encadeadas.
Merge Sort em C
void intercalar(int v[], int ini, int meio, int fim) {
int n1 = meio - ini + 1, n2 = fim - meio;
int e[n1], d[n2];
for (int i = 0; i < n1; i++) e[i] = v[ini + i];
for (int j = 0; j < n2; j++) d[j] = v[meio + 1 + j];
int i = 0, j = 0, k = ini;
while (i < n1 && j < n2) v[k++] = (e[i] <= d[j]) ? e[i++] : d[j++];
while (i < n1) v[k++] = e[i++];
while (j < n2) v[k++] = d[j++];
}
void merge_sort(int v[], int ini, int fim) {
if (ini >= fim) return;
int meio = (ini + fim) / 2;
merge_sort(v, ini, meio);
merge_sort(v, meio + 1, fim);
intercalar(v, ini, meio, fim);
}Merge Sort em Python
def merge_sort(v):
if len(v) <= 1:
return v
meio = len(v) // 2
esq = merge_sort(v[:meio])
dir = merge_sort(v[meio:])
res, i, j = [], 0, 0
while i < len(esq) and j < len(dir):
if esq[i] <= dir[j]:
res.append(esq[i]); i += 1
else:
res.append(dir[j]); j += 1
return res + esq[i:] + dir[j:]Merge Sort em Java
static void mergeSort(int[] v, int ini, int fim) {
if (ini >= fim) return;
int meio = (ini + fim) / 2;
mergeSort(v, ini, meio);
mergeSort(v, meio + 1, fim);
int[] aux = new int[fim - ini + 1];
int i = ini, j = meio + 1, k = 0;
while (i <= meio && j <= fim) aux[k++] = v[i] <= v[j] ? v[i++] : v[j++];
while (i <= meio) aux[k++] = v[i++];
while (j <= fim) aux[k++] = v[j++];
System.arraycopy(aux, 0, v, ini, aux.length);
}Quer comparar com outros métodos? No visualizador de algoritmos de ordenação você roda todos no mesmo vetor e compara o número de comparações e trocas.
Perguntas Frequentes
Qual a complexidade do Merge Sort?
O(n log n) em todos os casos. O vetor é dividido log n vezes, e em cada nível da recursão a intercalação percorre os n elementos.
O Merge Sort é estável?
Sim, desde que a intercalação copie da metade esquerda quando os elementos forem iguais (usando <= na comparação).
Qual a desvantagem do Merge Sort?
Usa memória extra proporcional ao tamanho do vetor, O(n), para a intercalação. O Quick Sort e o Heap Sort ordenam no próprio vetor.