Algoritmos em Python

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.

  • Intermediário
  • 3 min de leitura
  • 1 exemplo executável

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.

Das provas ao código
if len(values) <= 1:📄 Uma prova sozinha já está ordenada
merge_sort(values[:middle])✂️ Divida a pilha e ordene cada metade
left[left_index] <= right[right_index]🤝 Junte: pegue a prova de cima menor
result + left[left_index:] + right[right_index:]📚 Acrescente o que sobrou da outra pilha
Divida até itens únicos e depois junte as pilhas ordenadas.
Em uma frase

O 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

  1. if len(values) <= 1: return values é o caso base que para a recursão.
  2. merge_sort(values[:middle]) e merge_sort(values[middle:]) ordenam as duas metades.
  3. O laço while pega o menor valor da frente de left ou right até uma das listas acabar.
  4. left[left_index:] e right[right_index:] acrescentam os valores restantes, que já estão ordenados.
  5. <= 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

Executar código →
main.py
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]))
Gerar um botão Run para este exemplo

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.

  1. Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
  2. Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
  3. Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Executar no compilador Python →

Erros comuns

Esquecer as sobras

Quando uma metade acaba, o resto da outra metade é perdido.

Problema
return result
Correção
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