Ordenação por intercalação (merge sort) em Python
Nesta lição, você vai implementar o merge sort com a estratégia de dividir para conquistar usando uma função recursiva.
Introdução
O problema
Ordenações simples ficam muito lentas quando a lista cresce: dobrar os dados quadruplica o trabalho. O merge sort divide o problema em problemas menores, fáceis de resolver, e faz o trabalho crescer só um pouco mais rápido que os dados.
Pense assim
O merge sort é como ordenar uma pilha grande de provas com amigos. Você divide a pilha ao meio, entrega cada metade a alguém, e cada um divide de novo, até todos segurarem uma prova só. Então duplas juntam suas pilhas ordenadas pegando sempre a prova de cima menor, até sobrar uma única pilha ordenada.
if len(values) <= 1:📄 Uma prova sozinha já está ordenadamerge_sort(values[:middle])✂️ Divida a pilha e ordene cada metadeleft[left_index] <= right[right_index]🤝 Junte: pegue a prova de cima menorresult + left[left_index:] + right[right_index:]📚 Acrescente o que sobrou da outra pilhaO merge sort divide uma lista ao meio, ordena cada metade recursivamente e junta (merge) as duas metades ordenadas. Ele leva tempo O(n log n).
Pontos-chave
if len(values) <= 1: return valuesé o caso base que para a recursão.merge_sort(values[:middle])emerge_sort(values[middle:])ordenam as duas metades.- O laço
whilepega o menor valor da frente deleftourightaté uma das listas acabar. left[left_index:]eright[right_index:]acrescentam os valores restantes, que já estão ordenados.<=pega primeiro da esquerda em caso de empate, o que mantém valores iguais na ordem original.
Quando usar?
- Ordenar dados grandes de forma previsivelmente rápida, sem um pior caso ruim.
- Ordenar listas encadeadas ou dados grandes demais para a memória (ordenação externa).
- Aprender dividir para conquistar, um padrão usado em muitos algoritmos.
Quando não é preciso
- Código Python normal:
sorted()já usa o Timsort, uma mistura ajustada de merge sort e insertion sort. - Memória muito apertada: o merge sort precisa de espaço extra para as listas juntadas.
Visualizador de Ordenação por intercalação (merge sort) em Python
O(n log n)Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.
Código de exemplo
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Resultado da execução
[3, 9, 10, 27, 38, 43, 82]
Explicação do código
A função recursiva divide a lista até que cada parte tenha um único elemento, já que uma lista de um elemento está sempre ordenada. Depois, o laço while intercala as duas sublistas pegando sempre o menor elemento do início de cada uma. O algoritmo sempre roda em tempo O(n log n) e precisa de O(n) de memória extra.
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Esquecer as sobras
Quando uma metade acaba, o resto da outra metade é perdido.
return result
return result + left[left_index:] + right[right_index:]
Terminou esta lição?
Marque como aprendida para acompanhar seu progresso.
Pratique com um desafio
Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.
Todos os desafios