Ordenando Arrays com NodeJS e Javascript

array.sort() sem comparador ordena como string — [10, 2, 1].sort() vira [1, 10, 2]. Entender bubble, merge e quick é o que te salva em entrevista e em debug de performance.

O que você vai aprender:

• Bubble, merge e quick em código
• Complexidade média e pior caso
• Estabilidade e quando importa
• Usar Array.sort com comparador correto

Pré-requisitos: arrays (ep. 2).

Algoritmos de ordenação: bubble, merge e quick

Ordenação é uma das operações mais fundamentais da computação. Você provavelmente usa Array.sort() todo dia sem pensar—mas você sabe o que ele está fazendo de verdade? Sabe por que ordenar um milhão de números é rápido mas um bilhão é muito, muito mais lento? E sabe quando o sort nativo pode te dar resultados errados silenciosamente?

É disso que trata esse post. A gente vai implementar alguns algoritmos clássicos de ordenação, entender as diferenças de performance e terminar com dicas pra usar o sort nativo do JavaScript corretamente.

Um Pouco de Teoria Antes

Antes de escrever qualquer código, vamos ver o quadro de Big-O:

Alguns conceitos-chave:

• Sort estável: se dois elementos são iguais, eles mantêm a ordem relativa original. Isso importa quando você ordena objetos por uma propriedade e quer que outra propriedade fique na ordem anterior.
• In-place: o algoritmo ordena dentro do mesmo array sem alocar memória extra. Bubble sort e quick sort são in-place; merge sort precisa de espaço extra.

Veja como o merge sort divide e une:

graph TD
  A["[38, 27, 43, 3]"]
  B["[38, 27]"]
  C["[43, 3]"]
  D["[38]"]
  E["[27]"]
  F["[43]"]
  G["[3]"]
  H["[27, 38]"]
  I["[3, 43]"]
  J["[3, 27, 38, 43]"]

  A --> B
  A --> C
  B --> D
  B --> E
  C --> F
  C --> G
  D --> H
  E --> H
  F --> I
  G --> I
  H --> J
  I --> J

Divide até ter elementos únicos (que estão trivialmente ordenados), depois une os pares de volta—sempre em ordem.

Mão na Massa

Agora a Prática

Cria um arquivo chamado sort.js e vamos começar com o algoritmo mais simples:

Bubble Sort

function bubbleSort(arr) {
  const a = [...arr] // não muta o original
  const n = a.length
  for (let i = 0; i < n - 1; i++) {
    let swapped = 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]]
        swapped = true
      }
    }
    if (!swapped) break // já ordenado — melhor caso O(n)
  }
  return a
}

O bubble sort funciona trocando repetidamente elementos adjacentes que estão fora de ordem. Depois de cada passagem completa, o maior elemento não ordenado "borbulhou" pra sua posição correta no final. O flag swapped é uma otimização: se nenhuma troca aconteceu numa passagem completa, o array já está ordenado e podemos parar.

Merge Sort

function mergeSort(arr) {
  if (arr.length <= 1) return arr
 
  const mid = Math.floor(arr.length / 2)
  const left = mergeSort(arr.slice(0, mid))
  const right = mergeSort(arr.slice(mid))
 
  return merge(left, right)
}
 
function merge(left, right) {
  const result = []
  let l = 0
  let r = 0
 
  while (l < left.length && r < right.length) {
    if (left[l] <= right[r]) {
      result.push(left[l++])
    } else {
      result.push(right[r++])
    }
  }
 
  return result.concat(left.slice(l)).concat(right.slice(r))
}

Merge sort é um algoritmo clássico de dividir e conquistar:

1. Dividir: divide o array ao meio recursivamente até cada pedaço ter um elemento.
2. Conquistar: une pares de pedaços ordenados de volta, sempre escolhendo o menor elemento da frente.

É estável e sempre O(n log n), mas precisa de memória extra proporcional ao tamanho da entrada.

Sort nativo

// Lexicográfico por padrão (NÃO use sem comparador pra números!)
[10, 9, 2, 100].sort()           // [10, 100, 2, 9] — ERRADO pra números!
 
// Numérico crescente correto
[10, 9, 2, 100].sort((a, b) => a - b)   // [2, 9, 10, 100]
 
// Numérico decrescente correto
[10, 9, 2, 100].sort((a, b) => b - a)   // [100, 10, 9, 2]
 
// Ordenar objetos por uma propriedade
const users = [
  { name: 'Charlie', age: 30 },
  { name: 'Alice', age: 25 },
  { name: 'Bob', age: 28 },
]
users.sort((a, b) => a.age - b.age)
// [Alice (25), Bob (28), Charlie (30)]

Agora vamos fazer um teste completo. Adiciona isso depois das funções:

const nums = [38, 27, 43, 3, 9, 82, 10]
 
console.log('Original:', nums)
console.log('Bubble sort:', bubbleSort(nums))
console.log('Merge sort:', mergeSort(nums))
console.log('Sort nativo (errado — lexicográfico):', [...nums].sort())
console.log('Sort nativo (correto — numérico):', [...nums].sort((a, b) => a - b))

Roda:

node sort.js

Resultado esperado:

Original: [
  38, 27, 43,  3,
   9, 82, 10
]
Bubble sort: [
   3,  9, 10, 27,
  38, 43, 82
]
Merge sort: [
   3,  9, 10, 27,
  38, 43, 82
]
Sort nativo (errado — lexicográfico): [
  10, 27,  3, 38,
  43,  9, 82
]
Sort nativo (correto — numérico): [
   3,  9, 10, 27,
  38, 43, 82
]

As três implementações corretas produzem [3, 9, 10, 27, 38, 43, 82]. E viu o sort nativo "errado"? Esse é o bug clássico—Array.sort converte elementos pra string por padrão, então 10 vem antes de 3 porque "1" < "3" lexicograficamente. Sempre passe um comparador ao ordenar números.

Aonde Você Pode Usar/Ver

Pré-processamento Antes de Busca Binária

Busca binária (próximo post!) requer um array ordenado. Se você tem um conjunto de dados desordenado e precisa fazer várias buscas nele, ordenar uma vez com O(n log n) e depois fazer buscas O(log n) é um ganho enorme em comparação com varreduras lineares O(n) toda vez.

Renderizando Listas Ordenadas

Tabelas de UI, placar de líderes, rankings de feed, resultados de busca—quase toda lista mostrada ao usuário foi ordenada antes de renderizar. Entender estabilidade de sort importa quando você encadeia sorts: ordena por data primeiro, depois por score, e quer que empates em score preservem a ordem de data.

Pipelines de Processamento de Dados

Pipelines ETL, engines de analytics e ferramentas de relatório frequentemente ordenam dados como passo intermediário—agrupando registros antes de agregação, ordenando eventos pra replay, encontrando duplicatas trazendo valores iguais para adjacência.

Edge cases: comparador e mutação

sort() muta o array. Precisa do original? [...arr].sort((a,b) => a - b).

Objetos: comparador deve retornar negativo/zero/positivo — não boolean.

Números: sempre (a, b) => a - b, nunca confiar no sort lexicográfico padrão.

TL;DR — Ordenação

Próximos passos

• Busca binária (ep. 16): exige array ordenado — Implementando busca binária
• ECMAScript: sort estável desde ES10 — Novidades ES7–ES10

Antes de fechar

Qual algoritmo sua linguagem usa no sort nativo? Se viu cagada no post ou tem benchmark local, comenta.