Merge sort
O merge sort transforma um problema difícil em muitos fáceis: duas listas ordenadas são simples de juntar numa só. Divida a lista ao meio até cada pedaço ser um único valor e depois volte a fundir os pedaços. É o algoritmo clássico de divisão e conquista, e o seu tempo é n log n, seja qual for a entrada.
A ideia
Fundir é a parte fácil. Dadas duas listas, cada uma já ordenada, compare os seus primeiros valores e tire o menor. Compare os novos primeiros valores e volte a tirar o menor. Quando uma lista acabar, junte o resto da outra. Cada passo tira um valor, por isso fundir duas listas com comprimento total m exige no máximo m − 1 comparações. O merge sort usa isto para ordenar: divida a lista ao meio, ordene cada metade com merge sort e funda as duas metades.
Um exemplo
Pegue em 5, 1, 4, 2, 8. Divida em 5, 1 e 4, 2, 8. A primeira metade divide-se em 5 e 1, que se fundem em 1, 5. A segunda metade divide-se em 4 e 2, 8; o 2, 8 resulta da fusão de 2 e 8 e depois funde-se com 4 em 2, 4, 8. Por fim, 1, 5 e 2, 4, 8 fundem-se: 1, depois 2, depois 4, depois 5, e sobra o 8. São 8 comparações, 12 escritas e 4 fusões.
Porquê n log n
Cada divisão corta os pedaços ao meio, por isso, após cerca de log₂ n níveis, cada pedaço é um único valor. No regresso, cada nível de fusões trata cada valor uma vez: n escritas e menos de n comparações por nível. No total, são cerca de n log₂ n. Para 40 valores, a ordenação faz 216 escritas e no máximo 177 comparações; o bubble sort pode precisar de 780 comparações para a mesma lista. A ordem da entrada importa muito menos do que nesses algoritmos: para 40 valores, uma lista ordenada exige 100 comparações, uma invertida 116 e uma aleatória cerca de 160.
O buffer e a estabilidade
Para fundir duas metades que estão lado a lado na lista, o método habitual copia-as para um buffer e volta a escrevê-las por ordem. A aplicação mostra esse buffer como a segunda linha de barras. Precisa de tanta memória extra como a lista, e esse é o principal custo do merge sort. Em troca, a ordenação é estável: quando os dois primeiros valores são iguais, vai primeiro o da metade esquerda, por isso os valores iguais mantêm a sua ordem. A estabilidade importa quando se ordenam registos por um campo e depois por outro.
História e utilização
John von Neumann descreveu o merge sort em 1945, o que faz dele um dos primeiros algoritmos escritos para um computador de programa armazenado. Como lê e escreve os dados em longas sequências, foi o método padrão para ordenar dados em fita e ainda é usado para ficheiros demasiado grandes para a memória. O Timsort, usado pelo Python e pelo Java para objetos, é um merge sort que primeiro procura sequências já ordenadas e usa o insertion sort para pedaços curtos.
Experimente
Abra a aplicação e prima Avançar. A parte sombreada da lista está a ser dividida ou fundida, e a linha tracejada marca o meio. Quando começa uma fusão, as duas metades descem para a linha do buffer; os dois primeiros valores são comparados e o menor volta a subir. Veja os contadores: as escritas são as mesmas para qualquer lista do mesmo comprimento, e as comparações são mínimas para uma lista ordenada ou invertida e máximas para uma aleatória, mas nunca mais do que cerca de n log₂ n.
Perguntas frequentes
Qual é a complexidade temporal do merge sort?
O(n log n) no melhor caso, no caso médio e no pior caso. A versão habitual precisa de O(n) de memória extra para o buffer.
Qual é a diferença entre o merge sort e o quicksort?
Ambos dividem a lista e ordenam as partes. O merge sort divide ao meio sem olhar para os valores e faz o trabalho na fusão; o quicksort faz o trabalho na divisão, movendo valores em torno de um pivô, e não precisa de fusão. O quicksort ordena no próprio lugar e é muitas vezes mais rápido na prática, mas pode abrandar até n² com entradas desfavoráveis e não é estável. O merge sort é sempre n log n e estável.
O que é o merge sort bottom-up?
Uma versão sem recursão: primeiro funde valores isolados vizinhos em pares, depois pares em grupos de quatro, e assim por diante, duplicando o comprimento a cada ronda. Faz o mesmo trabalho que a versão top-down mostrada aqui.
O merge sort é estável?
Sim, desde que, em caso de empate, se tire primeiro o valor da metade esquerda, como faz esta aplicação.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimentar o merge sort