Comparações
Escritas
Fusões

  • Parte em fusão
  • Comparados
  • Reescritos
  • Já fundidos

Mais sobre o merge sort

Merge sort

O merge sort (ordenação por fusão) é um algoritmo de divisão e conquista. Divide a lista ao meio, ordena cada metade da mesma forma e funde as duas metades ordenadas tirando sempre o menor dos primeiros valores. Veja as metades passarem para uma linha de buffer e voltarem por ordem, a qualquer velocidade ou um passo de cada vez, e conte comparações, escritas e fusões. Prima Reproduzir para ver a ordenação, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Os contadores mostram comparações, escritas na lista e fusões. Escolha quantas barras, como começam, ou escreva os seus próprios números. Com o quadro selecionado, as setas avançam e recuam, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Escolha o número de barras e a ordem inicial: aleatória, quase ordenada, invertida ou com poucos valores distintos. Ou escreva os seus próprios números.
  2. Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto da ordenação.
  3. Acompanhe cada fusão: as duas metades ordenadas descem para o buffer, e o menor dos primeiros valores volta a subir, um de cada vez.

Como funciona o merge sort

Um único valor já está ordenado. Para qualquer lista mais longa, divida-a em duas metades e ordene cada metade com merge sort. Depois funda-as: olhe para o primeiro valor de cada metade, passe o menor para o resultado e repita até as duas metades ficarem vazias. Como as duas metades estão ordenadas, o resultado também fica ordenado.

Sempre n log n

Dividir ao meio vezes sem conta dá cerca de log₂ n níveis, e cada nível de fusões escreve cada valor uma vez, por isso a ordenação faz cerca de n log₂ n escritas e, no máximo, outras tantas comparações. Ao contrário do bubble sort, do selection sort e do insertion sort, isto não cresce com n², e a ordem da lista importa muito menos. O custo é um buffer tão longo como a lista. O merge sort é também estável, e é por isso que está na base das ordenações de Python e Java.

Perguntas frequentes

Como funciona o merge sort?

Divide a lista ao meio, ordena cada metade com merge sort e funde as duas metades ordenadas tirando sempre o menor dos seus primeiros valores. Uma lista de um só valor já está ordenada, por isso a divisão para aí.

Quantas comparações faz o merge sort?

Para n valores, no máximo cerca de n log₂ n − n + 1 e, no mínimo, cerca de metade de n log₂ n. Para 40 valores, são no máximo 177. As escritas na lista são sempre as mesmas para um dado n: uma por valor em cada nível de fusão.

Porque é que o merge sort precisa de memória extra?

Fundir duas metades no próprio lugar é difícil de fazer depressa, por isso o merge sort habitual copia as metades para um buffer e volta a escrevê-las por ordem. O buffer é tão longo como a lista, e essa é a principal desvantagem face ao quicksort e ao heap sort.

O merge sort é estável?

Sim. Quando os dois primeiros valores são iguais, vai primeiro o da metade esquerda, por isso os valores iguais mantêm a ordem original.

Os meus números são enviados para algum lado?

Não. A ordenação corre no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor