Ordenação 2: merge sort e quicksort

Ordenar um milhão de valores comparando todos os pares leva cerca de 500 bilhões de comparações; o merge sort precisa de cerca de 20 milhões.

Divida o problema, resolva as metades

Os métodos da unidade anterior trabalham com a lista inteira de uma vez e pagam por isso com cerca de n² comparações. Os dois métodos desta unidade usam outro plano, chamado dividir para conquistar. Divida a lista em partes menores, ordene cada parte com o mesmo método e depois combine as partes ordenadas. A divisão continua até uma parte ter um valor ou nenhum, e uma lista de um valor já está ordenada. Como o método chama a si mesmo em listas menores, ele é recursivo (a unidade 6 trata da recursão em detalhe).

Merge sort: o trabalho está na intercalação

O merge sort (ordenação por intercalação) corta a lista ao meio, ordena a metade esquerda, ordena a metade direita e intercala as duas metades ordenadas numa só. A parte esperta é a intercalação. Duas listas ordenadas podem ser combinadas olhando só os valores da frente. Compare as duas frentes, anote o menor e passe para o seguinte. Repita até uma lista ficar vazia e depois copie o que sobrou da outra. Intercalar [1, 4, 7] e [2, 3, 8] dá 1 (1 contra 2), 2 (4 contra 2), 3 (4 contra 3), 4 (4 contra 8), 7 (7 contra 8), e então o 8 é copiado: 5 comparações para 6 valores. Uma intercalação de duas listas com n valores no total nunca precisa de mais de n − 1 comparações.

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (right[j] < left[i]) out.push(right[j++]);
    else out.push(left[i++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

function mergeSort(a) {
  if (a.length <= 1) return a;          // já está ordenada
  const mid = Math.floor(a.length / 2);
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

Por que isso é rápido? Imagine os cortes ao meio como níveis. Uma lista de 8 valores se divide em 2 listas de 4, depois 4 listas de 2, depois 8 listas de 1: três níveis, porque 8 pode ser cortado ao meio 3 vezes. Em cada nível, todas as intercalações juntas tocam cada valor uma vez, então um nível custa no máximo cerca de n comparações. Com log₂ n níveis, o total fica em torno de n log₂ n. Para um milhão de valores isso dá cerca de 20 milhões de comparações, contra cerca de 500 bilhões dos métodos que comparam par a par. Dividida como [38, 27, 43, 3] e [9, 82, 10], como no laboratório, a lista [38, 27, 43, 3, 9, 82, 10] leva 14 comparações; o código acima a divide em 3 e 4 e leva 13.

O preço é a memória. A intercalação precisa de um lugar para escrever a saída, então o merge sort usa uma segunda lista do tamanho da entrada. O merge sort também é estável: valores que são iguais na comparação mantêm a ordem original, porque a intercalação pega da lista esquerda quando as frentes são iguais. Isso importa quando você ordena uma tabela por uma coluna depois da outra, por exemplo por cidade e depois por nome.

Quicksort: divida em torno de um pivô

O quicksort divide a lista de outro jeito. Ele escolhe um valor, o pivô, e rearranja a lista para que tudo o que é menor que o pivô venha antes dele e todo o resto venha depois. Esse passo se chama particionamento. Agora o pivô está no lugar final, e os dois lados podem ser ordenados separadamente com o mesmo método. Não é preciso intercalar nada depois, porque todo valor da esquerda já é menor que todo valor da direita.

O laboratório usa uma versão comum dos livros didáticos, que pega o último valor de cada parte como pivô. Em [5, 1, 4, 2, 8], o pivô 8 é comparado com os outros quatro valores, todos menores, então o 8 fica no fim. A parte seguinte, [5, 1, 4, 2], usa o pivô 2: só o 1 é menor, então depois de duas trocas a lista fica [1, 2, 4, 5, 8]. Mais uma comparação resolve [4, 5]. Total: 8 comparações e 2 trocas.

Quando o pivô cai perto do meio, cada divisão corta o problema ao meio e o quicksort leva cerca de n log₂ n comparações, como o merge sort. Ele também trabalha dentro da lista original, sem uma segunda cópia. Mas um pivô ruim atrapalha. Se a lista já está ordenada e o pivô é sempre o último valor, cada divisão separa só um valor, e o quicksort volta a cerca de n²/2 comparações: 10 para [1, 2, 3, 4, 5], o mesmo que o selection sort. As bibliotecas de verdade evitam isso escolhendo o pivô com mais cuidado, por exemplo ao acaso ou como o do meio entre três valores de amostra.