Quicksort × mesclagem
A ordenação por mesclagem (merge sort) também divide para conquistar: parte a lista ao meio, ordena cada metade e junta as duas já ordenadas. Ela é O(n log n) sempre, enquanto o quicksort é O(n log n) no caso médio e O(n²) no pior caso. Compare quantas comparações cada um faz.
Explicação do algoritmo: escolha um nível para ler.
{ }Ver o código
function mesclagem(lista) {
if (lista.length < 2) return lista; // caso base
const meio = Math.floor(lista.length / 2);
const esquerda = mesclagem(lista.slice(0, meio));
const direita = mesclagem(lista.slice(meio));
return juntar(esquerda, direita);
}
// junta duas listas já ordenadas
function juntar(a, b) {
const resultado = [];
let i = 0;
let j = 0;
while (i < a.length && j < b.length) {
resultado.push(a[i] <= b[j] ? a[i++] : b[j++]);
}
return [...resultado, ...a.slice(i), ...b.slice(j)];
}Comparações em três tipos de entrada
| Entrada | Quicksort (pivô no meio) | Quicksort (pivô no primeiro) | Mesclagem |
|---|---|---|---|
| Aleatória | 621 | 610 | 548 |
| Já ordenada | 480 | 4.950 | 316 |
| Em ordem inversa | 480 | 4.950 | 356 |
Em vermelho, o valor muito pior que o melhor da linha. Com o pivô no primeiro elemento, uma lista já ordenada (ou inversa) faz o quicksort escolher sempre o menor ou o maior elemento: o pior caso, O(n²). A mesclagem não depende da ordem da entrada. Repare que, nas listas aleatórias, a mesclagem até faz menos comparações. Ainda assim, o livro afirma que o quicksort costuma ser mais rápido na prática: o tempo depende de mais do que comparações (como copiar e alocar listas e usar a memória), e esse custo por passo é a constante que o Big O não mostra (veja a página sobre constantes). Esta página conta só comparações, não mede tempo.
A mesclagem passo a passo
A árvore desce dividindo as listas ao meio até sobrar um elemento (caso base). Depois sobe juntando: as listas em verde são o resultado de cada junção.