Algoritmos e Estruturas de Dados · 1.º ano (indicativo)

Como implementar o merge sort passo a passo?

  • 9 min de leitura
  • 4 exemplos resolvidos
  • 5 exercícios com solução
  • Atualizado em

Resposta curta

O merge sort divide a lista ao meio, ordena cada metade com a própria função (recursão) e depois intercala as duas metades já ordenadas num único resultado ordenado. A recursão pára em listas de 0 ou 1 elemento. A complexidade é O(n log n) em todos os casos.

Quando se aplica

Usa-se o merge sort quando quer um algoritmo de ordenação previsível e estável: o tempo é O(n log n) mesmo no pior caso, e elementos iguais mantêm a ordem original. Aplica-se a ordenar notas, nomes, preços ou registos, e é a base de muitas ordenações de ficheiros grandes. Em troca, precisa de memória extra proporcional a n para guardar as listas intermédias.

Pré-requisitos

  • Funções e recursão em Python (uma função que se chama a si mesma, com caso de paragem).
  • Listas, ciclo while e fatias: v[:3] dá os 3 primeiros elementos e v[3:] dá os restantes.

A ideia em três ações

AçãoO que faz
Dividirparte a lista em duas metades
Conquistarordena cada metade, recursivamente
Combinarintercala as duas listas ordenadas

Método passo a passo

  1. Caso base: se a lista tem 0 ou 1 elemento, já está ordenada; devolva-a.
  2. Divida: calcule meio = len(v) // 2; a metade esquerda é v[:meio] e a direita é v[meio:].
  3. Ordene cada metade chamando merge_sort sobre ela.
  4. Intercale as duas listas ordenadas com a função merge: compare os primeiros elementos de cada uma, copie o menor para o resultado e avance nessa lista.
  5. Quando uma das listas acabar, acrescente o resto da outra.
  6. Devolva a lista resultante.

O código completo

A função merge_sort (Python). A coluna Recuo indica os níveis de indentação, com 4 espaços por nível.

LinhaRecuoCódigo
10def merge_sort(v):
21if len(v) <= 1:
32return v
41meio = len(v) // 2
51esq = merge_sort(v[:meio])
61direita = merge_sort(v[meio:])
71return merge(esq, direita)

A função merge, que intercala duas listas já ordenadas:

LinhaRecuoCódigo
10def merge(a, b):
21res = []
31i = 0
41j = 0
51while i < len(a) and j < len(b):
62if a[i] <= b[j]:
73res.append(a[i])
83i += 1
92else:
103res.append(b[j])
113j += 1
121res.extend(a[i:])
131res.extend(b[j:])
141return res

Nota

A comparação a[i] <= b[j] usa «menor ou igual» para escolher primeiro o elemento da lista esquerda em caso de empate. É isso que torna o algoritmo estável.

Exemplos resolvidos

Exemplo 1 — Intercalar duas listas ordenadas

Enunciado: Execute merge([2, 5, 9], [3, 4, 10]).

Resolução:

  1. Compare 2 e 3: copia 2. Resultado [2].
  2. Compare 5 e 3: copia 3. Resultado [2, 3].
  3. Compare 5 e 4: copia 4. Resultado [2, 3, 4].
  4. Compare 5 e 10: copia 5. Resultado [2, 3, 4, 5].
  5. Compare 9 e 10: copia 9. A primeira lista acabou.
  6. Acrescente o resto da segunda lista, [10].

Resposta: [2, 3, 4, 5, 9, 10]. Verificação: 6 elementos, ordem crescente, todos os valores originais presentes.

Exemplo 2 — Ordenar quatro elementos

Enunciado: Ordene [38, 27, 43, 3] com o merge sort.

Resolução:

  1. Divida: [38, 27] e [43, 3].
  2. Divida de novo: [38], [27], [43], [3]; todas ordenadas (um elemento).
  3. Intercale [38] com [27]: [27, 38]. Intercale [43] com [3]: [3, 43].
  4. Intercale [27, 38] com [3, 43]: 3 (menor), depois 27, depois 38 e por fim 43.

Resposta: [3, 27, 38, 43]. Verificação: cada elemento aparece uma vez e cada par vizinho está em ordem.

Exemplo 3 — Oito elementos com repetição

Enunciado: Ordene [5, 2, 4, 7, 1, 3, 2, 6].

Resolução:

  1. Metades: [5, 2, 4, 7] e [1, 3, 2, 6].
  2. Esquerda: [5, 2] dá [2, 5]; [4, 7] dá [4, 7]; intercalando, [2, 4, 5, 7].
  3. Direita: [1, 3] dá [1, 3]; [2, 6] dá [2, 6]; intercalando, [1, 2, 3, 6].
  4. Intercale [2, 4, 5, 7] com [1, 2, 3, 6]: 1; depois 2 (da esquerda, por empate); depois 2 (da direita); 3; 4; 5; 6; resta 7.

Resposta: [1, 2, 2, 3, 4, 5, 6, 7]. Verificação: 8 elementos; o 2 repetido aparece duas vezes.

Exemplo 4 — Nível de exame: contar o trabalho

Enunciado: Quantos níveis de divisão tem o merge sort para n = 8 e qual é o trabalho total aproximado? Qual a complexidade?

Resolução:

  1. Cada divisão parte a lista ao meio: 8 → 4 → 2 → 1. São 3 níveis, e 3 = log2 8.
  2. Em cada nível, a intercalação percorre todos os n = 8 elementos uma vez, ou seja, cerca de 8 operações.
  3. Trabalho total ≈ 8 × 3 = 24 operações.
  4. Em geral, n × log2 n.

Resposta: 3 níveis e cerca de 24 operações; complexidade O(n log n), em todos os casos. Verificação: para n = 1 024, log2 n = 10, e 1 024 × 10 = 10 240, contra mais de um milhão no caso de O(n2).

Erros frequentes

  • Esquecer o caso base (len(v) <= 1): a recursão nunca pára e dá RecursionError.
  • Dividir mal a lista: usar v[:meio] e v[meio + 1:] perde um elemento; as fatias devem ser v[:meio] e v[meio:].
  • Não acrescentar o resto depois do ciclo while: perdem-se os elementos que sobram numa das listas.
  • **Usar < em vez de <=** na comparação: o resultado continua ordenado, mas deixa de ser estável.
  • **Chamar merge com listas desordenadas:** a intercalação só funciona se as duas já estiverem ordenadas.
  • Achar que ordena no lugar: esta versão cria listas novas; devolva e use o resultado (v = merge_sort(v)).

Exercícios propostos

Tente resolver primeiro no caderno; depois confira.

1Exercício 1

Execute merge([1, 6, 8], [2, 3, 9]) e escreva o resultado.

Ver solução

Compare 1 e 2: 1. Compare 6 e 2: 2. Compare 6 e 3: 3. Compare 6 e 9: 6. Compare 8 e 9: 8. A primeira lista acabou; acrescenta-se [9]. Resultado: [1, 2, 3, 6, 8, 9].

2Exercício 2

Ordene [9, 4, 7, 1] com o merge sort, mostrando as divisões e as intercalações.

Ver solução

Divisão: [9, 4] e [7, 1]. Ordenando: [4, 9] e [1, 7]. Intercalação: 1 (da direita), 4, 7, 9. Resultado: [1, 4, 7, 9].

3Exercício 3

O que devolve merge([], [4])? E merge_sort([5])?

Ver dica

Veja o que acontece ao ciclo while quando uma lista é vazia.

Ver solução

Em merge([], [4]), a condição do while é falsa logo (a primeira lista não tem elementos); depois res.extend(b[0:]) acrescenta o 4: devolve [4]. merge_sort([5]) tem um elemento e devolve [5] pelo caso base.

4Exercício 4

Quantos níveis de divisão tem o merge sort para n = 16 e qual é o trabalho aproximado (n × níveis)?

Ver solução

16 → 8 → 4 → 2 → 1: 4 níveis, porque log2 16 = 4. Trabalho ≈ 16 × 4 = 64 operações.

5Exercício 5

Pretende-se ordenar os pares (nota, nome): (14, Ana), (12, Rui), (14, Bela). Ordenando só pela nota, em ordem crescente, com o merge sort estável, qual é o resultado?

Ver dica

Em caso de empate, mantém-se a ordem original.

Ver solução

A nota 12 é a menor: (12, Rui). As duas notas 14 empatam e mantêm a ordem em que apareceram: Ana antes de Bela. Resultado: (12, Rui), (14, Ana), (14, Bela). Um algoritmo não estável poderia trocar Ana e Bela.

Perguntas frequentes

Quando devo preferir o merge sort ao quick sort?

Quando precisa de tempo garantido O(n log n) no pior caso ou de estabilidade, por exemplo ao ordenar registos por várias colunas seguidas. O quick sort costuma ser mais rápido na prática em memória e gasta menos espaço, mas pode chegar a O(n2) no pior caso.

Porque é que o merge sort usa memória extra?

Porque cada intercalação cria uma lista nova para o resultado. No total, o espaço auxiliar é proporcional a n, isto é, O(n).

Existe uma versão mais rápida de escrever em Python?

Para uso no dia a dia, a função embutida sorted() e o método lista.sort() já ordenam em O(n log n) e estão otimizados. Implementar o merge sort à mão serve para aprender o algoritmo.

Funciona com tamanhos que não são potência de 2?

Sim. Se a lista tiver 5 elementos, meio é 2: a esquerda fica com 2 e a direita com 3. A recursão continua até listas de um elemento, e a complexidade mantém-se O(n log n).

Resumo

  • O merge sort aplica dividir para conquistar: divide, ordena cada metade e intercala.
  • O caso base é a lista com 0 ou 1 elemento.
  • A função merge combina duas listas ordenadas comparando os primeiros elementos e copiando o menor.
  • Complexidade de tempo O(n log n) em todos os casos; espaço extra O(n).
  • É estável se, em caso de empate, escolher primeiro o elemento da esquerda (<=).

Onde aprofundar

  • O programa e o manual da sua cadeira de Algoritmos e Estruturas de Dados.
  • Cormen, Leiserson, Rivest e Stein, Introduction to Algorithms, capítulo sobre divisão e conquista (confirme a edição).
  • Sedgewick e Wayne, Algorithms, secção sobre mergesort.

Continue a estudar

1.º ano (indicativo)8 min

Como determinar a complexidade de um algoritmo?

Escolha o tamanho da entrada n, conte quantas vezes a operação principal se repete em função de n, mantenha só o termo que mais cresce e ignore as constantes. Um ciclo…

4 exemplos5 exercícios com solução

Ver tudo de Algoritmos e Estruturas de Dados