Merge sort: dividir e intercalar

As três fases do merge sort

O merge sort segue à risca o roteiro de dividir para conquistar. A fase de dividir é trivial: encontre o meio e parta a lista em duas metades, esquerda e direita. A fase de conquistar não faz nada de novo, apenas confia na recursão: para ordenar a metade esquerda, o algoritmo chama a si mesmo sobre ela; para a direita, idem. Essa confiança parece mágica, mas se sustenta no caso base. Quando uma metade encolhe até ter um único elemento, ela já está ordenada, porque um elemento sozinho não tem como estar fora de ordem. A recursão então para de descer e começa a subir, e é na subida que acontece o trabalho de verdade.

A fase que dá nome ao algoritmo é a combinação, a intercalação. Ao voltar da recursão, você tem em mãos duas metades já ordenadas e precisa fundi-las numa lista maior também ordenada. Aqui está a beleza: intercalar duas listas ordenadas é fácil e rápido. Você olha o primeiro elemento de cada metade, pega o menor dos dois, coloca no resultado e avança naquela metade. Repete até esvaziar as duas. Como cada elemento é olhado uma única vez, intercalar custa proporcional ao tamanho total. É essa intercalação barata, feita em cada nível da recursão, que dá ao merge sort o seu custo O(n log n).

A intercalação por dentro

Vale ver a intercalação em detalhe, porque é o coração do algoritmo. Imagine duas metades ordenadas: a esquerda é 2, 6 e a direita é 4, 8. Você mantém um marcador na frente de cada uma. Compara 2 com 4: o 2 é menor, vai para o resultado e o marcador da esquerda avança. Agora compara 6 com 4: o 4 é menor, vai para o resultado e o marcador da direita avança. Compara 6 com 8: o 6 vai. Sobrou só o 8 na direita, que entra por último. Resultado: 2, 4, 6, 8. Repare que você nunca voltou atrás nem comparou tudo com tudo; cada elemento foi visitado uma vez só.

FUNÇÃO intercalar(esquerda, direita)
  resultado <- []
  i <- 0   // marcador da esquerda
  j <- 0   // marcador da direita
  ENQUANTO i < tamanho(esquerda) E j < tamanho(direita) FAÇA
    SE esquerda[i] <= direita[j] ENTÃO
      adicionar(resultado, esquerda[i])
      i <- i + 1
    SENÃO
      adicionar(resultado, direita[j])
      j <- j + 1
    FIM
  FIM
  // um dos lados pode ter sobrado; joga o resto no fim
  adicionar_resto(resultado, esquerda, i)
  adicionar_resto(resultado, direita, j)
  RETORNE resultado
FIM

Dois marcadores caminham pelas metades ordenadas, escolhendo sempre o menor da frente. O que sobrar de um lado entra no fim.

O custo e o preço a pagar

Por que o merge sort é O(n log n)? Pense nos níveis da divisão. A lista de n itens vira duas de n meios, depois quatro de n quartos, e assim por diante, até sobrarem pedaços de um elemento. O número de níveis dessa descida é log n, porque a lista é partida ao meio a cada nível. Em cada nível, a intercalação de todos os pedaços daquele nível percorre no total os n elementos. Logo, são log n níveis, cada um custando n: o produto é n vezes log n. E, diferente do quick sort que você verá adiante, esse custo vale sempre, no melhor e no pior caso, porque a divisão pela metade não depende dos valores da lista.