Ordenação por intercalação
Divide a lista ao meio, ordena cada metade e depois junta as duas metades ordenadas numa só lista ordenada.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- sim
- não
Melhor caso: como o tempo cresce com o tamanho n da lista quando a entrada é a mais fácil para este algoritmo.
Caso médio: como o tempo costuma crescer com n. Com n², o dobro de valores demora cerca de quatro vezes mais; n log n cresce bem menos.
Pior caso: o crescimento com a entrada mais difícil. Útil quando a velocidade nunca pode cair.
Memória: quanta memória extra é necessária além da lista. 1 significa algumas variáveis; n, uma cópia da lista.
Estável: dois valores iguais mantêm a ordem original. Importa quando se ordena por um só campo de um registo.
Sem memória extra: ordena dentro da própria lista, sem uma segunda lista.
- a comparar
- a mover
- na posição final
Experimente: Escolha uma lista com poucos valores únicos. Se dois valores são iguais, tira-se primeiro o da metade esquerda, por isso a ordem mantém-se.
Como funciona
Vai dividindo a lista até cada pedaço ter um só valor, que já está ordenado. Depois junta os pedaços aos pares: compara o primeiro valor de cada um e tira o menor, e repete até acabar. A linha de cima na animação é o espaço extra usado ao juntar.
Quando é uma boa escolha
Quando é preciso rapidez que se mantenha boa mesmo no pior caso e os valores iguais têm de manter a ordem. O Python e o Java usam ambos uma versão deste método. O ponto fraco é a memória extra de que precisa.