8 min
← Voltar
1
0 XP

Merge Sort

Algoritmo de ordenação estável que usa dividir para conquistar, dividindo o array ao meio e intercalando as metades ordenadas.

MédiaO(n log n) / O(n)OrdenaçãoDividir e ConquistarEstável

Visualizador Interativo

Array[ 5, 3, 8, 4, 2, 7, 1, 6 ]Passo 1 / 49
5
0
L
3
1
L
8
2
L
4
3
L
2
4
R
7
5
R
1
6
R
6
7
R
Dividindo em:esquerda e direita
Velocidade:800ms
Historico de Passos
#0Dividindo [0..7] em [0..3] e [4..7]

Como Funciona

O Merge Sort divide o array ao meio repetidamente até ter subarrays de um elemento. Depois, intercala (merge) esses subarrays de volta, mantendo a ordem. O processo de intercalação compara os elementos dos dois subarrays ordenados e constrói o resultado elemento por elemento, sempre escolhendo o menor disponível. É um algoritmo estável (preserva a ordem relativa de elementos iguais) e tem complexidade garantida O(n log n), mas usa O(n) de espaço adicional.

“O Merge Sort garante O(n log n) em todos os casos porque sempre divide ao meio. A intercalação de dois arrays ordenados é O(n), e temos log n níveis de recursão.”

Passo a Passo

  1. Divide o array ao meio
  2. Aplica Merge Sort recursivamente em cada metade
  3. Quando chega em subarrays de 1 elemento, começa a intercalar
  4. A intercalação compara elementos das duas metades
  5. Sempre escolhe o menor para o resultado
  6. Copia elementos restantes quando uma metade acaba

Análise de Complexidade

⏱️Tempo
O(n log n)

Sempre divide ao meio (log n níveis) e intercala n elementos em cada nível.

Ver prova

T(n) = 2T(n/2) + O(n). Pelo Teorema Mestre: O(n log n)

💾Espaco
O(n)

Precisa de arrays temporários para a intercalação.

🎯Melhor Caso
O(n log n)

Mesmo com array já ordenado, ainda divide e intercala.

⚠️Pior Caso
O(n log n)

Complexidade garantida, independente da entrada.

Comparação com Outros Algoritmos

AlgoritmoTempoEspacoEstavelMelhor Para
Merge Sort(atual)O(n log n)O(n)SimGrandes datasets, estabilidade necessária
Quick SortO(n log n)O(log n)NaoUso geral, melhor performance média
Bubble SortO(n²)O(1)SimFins didáticos
Selection SortO(n²)O(1)NaoQuando trocas são caras

Dicas e Erros Comuns

  • Esquecer de copiar os elementos restantes após o loop principal do merge
  • Não criar cópias dos subarrays antes da intercalação
  • Confundir os índices durante a intercalação

Perguntas de Entrevista

Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.

Implementacao

python
1def merge_sort(array):Definição
2    if len(array) <= 1:Caso Base
3        return array
4 
5    mid = len(array) // 2Divisão
6    left = merge_sort(array[:mid])Chamadas Recursivas
7    right = merge_sort(array[mid:])Chamadas Recursivas
8 
9    return merge(left, right)Intercalação
10 
11 
12def merge(left, right):Intercalação
13    result = []
14    i = j = 0
15 
16    while i < len(left) and j < len(right):
17        if left[i] <= right[j]:Cópia da Esquerda
18            result.append(left[i])
19            i += 1
20        else:Cópia da Direita
21            result.append(right[j])
22            j += 1
23 
24    result.extend(left[i:])Elementos Restantes
25    result.extend(right[j:])Elementos Restantes
26 
27    return result
28