Algoritmos de ordenação

Os principais

• Insertion sort — O(n²), mas ótimo para listas pequenas ou quase ordenadas (O(n) se já estiver em ordem).
• Merge sort — O(n log n) sempre e estável; usa O(n) de memória extra.
• Quicksort — O(n log n) na média, rápido na prática e sem memória extra, mas O(n²) com pivô ruim (por exemplo, sempre o menor).
• Heapsort — O(n log n) sempre, sem memória extra, não estável.

O que sua linguagem usa

Para objetos, Java/Kotlin (sortedBy, sortWith), Python e o V8 (Chrome, Node) usam Timsort: um merge sort que aproveita trechos já ordenados e usa insertion sort nos pedaços pequenos. É estável e O(n log n). O sort() do Swift também é estável. Raramente vale escrever o seu.

Estabilidade

Um sort estável mantém a ordem original entre itens iguais. Isso permite ordenar por vários critérios: ordene por nome e depois, de forma estável, por cidade — dentro de cada cidade os nomes continuam em ordem. Nenhum sort por comparação faz melhor que O(n log n) no pior caso.

const notas = [10, 9, 1, 100];
notas.sort(); // [1, 10, 100, 9] — compara como texto!

const notas = [10, 9, 1, 100];
const ordenadas = notas.toSorted((a, b) => a - b); // [1, 9, 10, 100], sem mudar notas

// Vários critérios: cidade e, empatou, nome (sort estável)
alunos.sort((a, b) => a.cidade.localeCompare(b.cidade, 'pt-BR') || a.nome.localeCompare(b.nome, 'pt-BR'));