Algoritmos de ordenação: do bubble ao quicksort sem mistério

Em código de produção você raramente vai implementar ordenação à mão — Array.prototype.sort, sorted() e Arrays.sort cobrem 99% dos casos. Mas entender o que essas funções fazem por baixo ajuda a escolher estrutura de dados certa, a discutir performance em revisão de código e a passar em entrevistas técnicas. Este artigo cobre seis algoritmos clássicos com implementação real em JavaScript, tabela Big-O completa e o que linguagens populares usam internamente em 2026.

Complexidade de tempo e espaço (Big-O)

Big-O descreve como o tempo de execução cresce conforme o tamanho da entrada (n). Estabilidade significa que elementos com chave igual mantêm a ordem relativa original — importante quando você ordena objetos por uma chave e quer preservar a ordem prévia das demais.

Bubble Sort

Compara pares adjacentes e troca quando estão fora de ordem. Repete até nenhuma troca acontecer. Didaticamente útil, na prática é evitado: O(n²) no caso médio é proibitivo a partir de poucas milhares de entradas.

function bubbleSort(arr) {
  const a = [...arr];
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let trocou = false;
    for (let j = 0; j < n - i - 1; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        trocou = true;
      }
    }
    if (!trocou) break; // otimização: já está ordenado
  }
  return a;
}

Insertion Sort

Constrói o array ordenado um elemento por vez, inserindo cada novo na posição correta. Excelente para arrays pequenos (< 16 elementos) e quase ordenados — por isso aparece como subrotina em algoritmos híbridos modernos como TimSort.

function insertionSort(arr) {
  const a = [...arr];
  for (let i = 1; i < a.length; i++) {
    const chave = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > chave) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = chave;
  }
  return a;
}

Merge Sort

Divide o array recursivamente até listas de tamanho 1, depois funde os pares em ordem. Garante O(n log n) no pior caso e é estável — escolha padrão quando estabilidade importa (ordenar por chave secundária) ou quando o pior caso precisa ser previsível.

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

function merge(esq, dir) {
  const res = [];
  let i = 0, j = 0;
  while (i < esq.length && j < dir.length) {
    if (esq[i] <= dir[j]) res.push(esq[i++]);
    else res.push(dir[j++]);
  }
  return res.concat(esq.slice(i)).concat(dir.slice(j));
}

Quick Sort

Escolhe um pivô, particiona em menores e maiores, recursão em cada lado. Cache-friendly e rápido na prática — costuma vencer Merge Sort em dados que cabem em memória. Não é estável e tem O(n²) no pior caso (entrada já ordenada com pivô fixo), mitigado com pivô aleatório.

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivo = arr[Math.floor(Math.random() * arr.length)];
  const menores = arr.filter((x) => x < pivo);
  const iguais = arr.filter((x) => x === pivo);
  const maiores = arr.filter((x) => x > pivo);
  return [...quickSort(menores), ...iguais, ...quickSort(maiores)];
}

Heap Sort

Constrói um max-heap e extrai o máximo n vezes. Garante O(n log n) no pior caso com O(1) de espaço extra — útil em sistemas embarcados ou ambientes com memória restrita. Não é estável e na prática perde para Quick Sort em cache locality.

function heapSort(arr) {
  const a = [...arr];
  const n = a.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(a, n, i);
  for (let i = n - 1; i > 0; i--) {
    [a[0], a[i]] = [a[i], a[0]];
    heapify(a, i, 0);
  }
  return a;
}

function heapify(a, n, i) {
  let maior = i;
  const e = 2 * i + 1, d = 2 * i + 2;
  if (e < n && a[e] > a[maior]) maior = e;
  if (d < n && a[d] > a[maior]) maior = d;
  if (maior !== i) {
    [a[i], a[maior]] = [a[maior], a[i]];
    heapify(a, n, maior);
  }
}

O que linguagens populares usam internamente

• V8 (Node.js, Chrome): TimSort desde 2018 (Chrome 70 / Node 11), conforme o changelog oficial do V8. Antes era QuickSort, que não garantia estabilidade.
• Python: TimSort desde a versão 2.3 (2002). É o algoritmo nativo de sorted() e list.sort(), criado por Tim Peters para CPython.
• Java: Dual-Pivot Quicksort em Arrays.sort para primitivos; TimSort em Arrays.sort para objetos (estável).
• Rust: pdqsort (pattern-defeating quicksort) para slice::sort_unstable; TimSort adaptado para slice::sort.

TimSort é um híbrido de Merge Sort + Insertion Sort projetado para dados parcialmente ordenados (caso comum no mundo real). Esse é o motivo de Array.prototype.sort em JS moderno ser estável e performar bem mesmo em entradas grandes.

Quando escolher cada um

• Bubble e Selection: nunca em produção. Servem para didática e para testes de implementação manual em entrevistas.
• Insertion: arrays pequenos (< 50) ou quase ordenados; subrotina em TimSort.
• Merge: quando estabilidade importa e pior caso O(n log n) precisa ser garantido (ordenar registros por chave secundária, sort externo em arquivos grandes).
• Quick: padrão da maioria das linguagens em arrays in-memory; rápido na prática, mas precisa de pivô aleatório para evitar pior caso.
• Heap: ambientes com memória restrita ou quando você precisa do top-K (heap parcial sem ordenar tudo).

Perguntas frequentes

Fontes consultadas

• Introduction to Algorithms (CLRS), 4ª ed., MIT Press
• V8 blog — Getting things sorted in V8
• Python — Timsort description (Tim Peters)
• Visualgo — visualização interativa de sorting
• Big-O Cheat Sheet
• Java SE 21 — Arrays.sort docs