Algoritmos de ordenação em JavaScript: bubble, merge, quick e quando escolher cada um. Código comentado e complexidade na prática.
Jonathan Juliani
Engenheiro de Software Sr - Full Stack · WithClutch Inc. | Juliani Tecnologia
array.sort() sem comparador ordena como — vira . Entender bubble, merge e quick é o que te salva em entrevista e em debug de performance.
[10, 2, 1].sort()[1, 10, 2]O que você vai aprender:
Array.sort com comparador corretoPré-requisitos: arrays (ep. 2).
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.
Antes de escrever qualquer código, vamos ver o quadro de Big-O:
| Algoritmo | Melhor | Médio | Pior | Estável? |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Sim |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Sim |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | Não |
| Sort nativo | O(n log n) | O(n log n) | O(n log n) | Sim (V8 ≥ Node 11) |
Alguns conceitos-chave:
Veja como o merge sort divide e une:
scene: en/data-structures-in-a-nutshell/merge-sort-split-merge
Interactive Excalidraw view is not available in this build.
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.
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:
É 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.jsResultado 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.
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.
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 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.
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.
| Algoritmo | Média | Estável? | Produção |
|---|---|---|---|
| Bubble | O(n²) | Sim | Só didático |
| Merge | O(n log n) | Sim | Sim |
| Quick | O(n log n) | Não* | Sim (*variantes estáveis existem) |
Array.sort | O(n log n) | Sim (V8) | Use sempre com comparador |
sort estável desde ES10 — Novidades ES7–ES10Qual algoritmo sua linguagem usa no sort nativo? Se viu cagada no post ou tem benchmark local, comenta.
Receba notas de arquitetura e performance na sua caixa de entrada. Mesma lista do convite—inscreva-se aqui quando quiser.
