Merge sort em detalhe

Merge sort: dividir para conquistar

O merge sort é o exemplo por excelência da estratégia de dividir para conquistar. Tem uma complexidade de O(n log n), muito melhor que o O(n²) do bubble sort para entradas grandes, e é estável (mantém a ordem relativa de elementos iguais).

A ideia se resume em três passos:

1. Dividir: parte o array ao meio até chegar a pedaços de tamanho 0 ou 1, que já estão ordenados por definição (o caso base).
2. Conquistar: ordena cada metade de forma recursiva.
3. Combinar: funde (merge) as duas metades já ordenadas em um único array ordenado.

A função merge

O coração do algoritmo é fundir dois arrays já ordenados em um só. Usamos dois índices (um por array) e vamos sempre escolhendo o menor dos dois elementos pendentes:

function merge(esq, dir) {
  const resultado = [];
  let i = 0;
  let j = 0;
  while (i < esq.length && j < dir.length) {
    if (esq[i] <= dir[j]) {
      resultado.push(esq[i]);
      i++;
    } else {
      resultado.push(dir[j]);
      j++;
    }
  }
  // Um dos dois já se esgotou; adicionamos o que restar do outro.
  return resultado.concat(esq.slice(i)).concat(dir.slice(j));
}

A função mergeSort

Com merge resolvido, mergeSort só divide e delega:

function mergeSort(arr) {
  if (arr.length <= 1) return [...arr]; // caso base

  const meio = Math.floor(arr.length / 2);
  const esq = mergeSort(arr.slice(0, meio));
  const dir = mergeSort(arr.slice(meio));
  return merge(esq, dir);
}

Repare que slice cria cópias: o algoritmo não muta o array original. Por que O(n log n)? Há log n níveis de divisão, e em cada nível se processam no total n elementos ao fundir.

Exemplos

Merge sort com rastreamento das divisões

function merge(esq, dir) {
  const out = [];
  let i = 0, j = 0;
  while (i < esq.length && j < dir.length) {
    if (esq[i] <= dir[j]) out.push(esq[i++]);
    else out.push(dir[j++]);
  }
  return out.concat(esq.slice(i)).concat(dir.slice(j));
}
function mergeSort(arr) {
  if (arr.length <= 1) return [...arr];
  const meio = Math.floor(arr.length / 2);
  console.log("Divido:", arr.slice(0, meio), "|", arr.slice(meio));
  return merge(mergeSort(arr.slice(0, meio)), mergeSort(arr.slice(meio)));
}
console.log("Ordenado:", mergeSort([5, 2, 8, 1, 9, 3]));