Dividir e ConquistarIntermediário

Merge Sort

Divide o array ao meio recursivamente, então intercala as partes ordenadas — garantindo O(n log n) mesmo no pior caso.

Tempo:O(n log n)

Espaço:O(n)

Como Funciona

Passo a passo do algoritmo

Divida o array ao meio

Encontre o ponto médio e divida o array em duas metades. Continue dividindo recursivamente até ter subarrays de um único elemento.

meio = (baixo + alto) / 2
mergeSort(array, baixo, meio)
mergeSort(array, meio+1, alto)

Caso base: array de um elemento

Um array com zero ou um elemento já está ordenado — é o caso base da recursão. A divisão para aqui.

se baixo >= alto: retorne

Intercale as duas metades ordenadas

Com as duas metades ordenadas, compare os menores elementos de cada uma. O menor vai para o array resultante. Repita até esgotar uma das metades.

enquanto i < esq.tamanho e j < dir.tamanho:
  se esq[i] ≤ dir[j]: resultado.add(esq[i++])
  senão: resultado.add(dir[j++])

Copie os elementos restantes

Quando uma das metades se esgotar, copie todos os elementos restantes da outra metade para o resultado — eles já estão ordenados.

copiar restante de esq[] ou dir[] para resultado

Combine os resultados

O processo de divisão e intercalação acontece em todos os níveis da recursão. No topo, o array inteiro estará ordenado após a intercalação final.

// Complexidade: O(n log n) em todos os casos

Implementação

Código comentado em JavaScript e Python

function mergeSort(array) {
  // Caso base: array de 0 ou 1 elementos já está ordenado
  if (array.length <= 1) return array;

  // Divide o array ao meio
  const meio = Math.floor(array.length / 2);
  const esquerda = array.slice(0, meio);
  const direita = array.slice(meio);

  // Ordena recursivamente cada metade e intercala
  return intercalar(mergeSort(esquerda), mergeSort(direita));
}

function intercalar(esquerda, direita) {
  const resultado = [];
  let i = 0, j = 0;

  // Compara e intercala enquanto há elementos nas duas metades
  while (i < esquerda.length && j < direita.length) {
    if (esquerda[i] <= direita[j]) {
      resultado.push(esquerda[i]);
      i++;
    } else {
      resultado.push(direita[j]);
      j++;
    }
  }

  // Copia elementos restantes (já ordenados)
  return [...resultado, ...esquerda.slice(i), ...direita.slice(j)];
}

// Exemplo de uso
const arr = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr)); // [3, 9, 10, 27, 38, 43, 82]

Playground

Observe a divisão e intercalação do Merge Sort em cada nível

merge-sort — passo 1 de 28

Metade esquerda

Metade direita

Intercalando

Ordenado

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Iniciando Merge Sort — dividindo o array em partes menores...

LentoRápido

Quando Usar

Cenários ideais para este algoritmo

Desempenho garantido

Quando você precisa de garantia de O(n log n) no pior caso — diferente do Quicksort que pode degradar para O(n²).

Ordenação externa (disco)

Ideal para ordenar dados maiores que a memória RAM — lê blocos do disco, ordena em memória e intercala sequencialmente.

Ordenação estável

Mantém a ordem relativa de elementos iguais — essencial quando a estabilidade importa (e.g., ordenar por múltiplos critérios).

Listas ligadas

Especialmente eficiente para listas ligadas — não precisa de acesso aleatório como outros algoritmos que usam índices.

Complexidade

Análise de desempenho por cenário

Cenário	Tempo	Descrição
Melhor caso	`O(n log n)`	Mesmo que o array já esteja ordenado, o Merge Sort sempre divide e intercala — log n níveis com n operações cada.
Caso médio	`O(n log n)`	O número de comparações e movimentos é sempre proporcional a n log n, independente da distribuição dos dados.
Pior caso	`O(n log n)`	Ao contrário do Quicksort, o Merge Sort garante O(n log n) mesmo no pior caso — por isso é usado em situações críticas.