Ordenação estável de `Array.prototype.sort`
Digamos que você tenha um array de cachorros, onde cada cachorro tem um nome e uma classificação. (Se isso parecer um exemplo estranho, você deve saber que existe uma conta no Twitter que se especializa exatamente nisso... Não pergunte!)
// Note como o array já está ordenado alfabeticamente por `nome`.
const doggos = [
{ name: 'Abby', rating: 12 },
{ name: 'Bandit', rating: 13 },
{ name: 'Choco', rating: 14 },
{ name: 'Daisy', rating: 12 },
{ name: 'Elmo', rating: 12 },
{ name: 'Falco', rating: 13 },
{ name: 'Ghost', rating: 14 },
];
// Ordene os cachorros por `rating` em ordem decrescente.
// (Isso atualiza `doggos` diretamente.)
doggos.sort((a, b) => b.rating - a.rating);
O array está pré-ordenado alfabeticamente por nome. Para ordenar por classificação (rating) em vez disso (para obter os cachorros com melhores classificações primeiro), usamos Array#sort, passando um callback personalizado que compara as classificações. Este é o resultado que você provavelmente esperaria:
[
{ name: 'Choco', rating: 14 },
{ name: 'Ghost', rating: 14 },
{ name: 'Bandit', rating: 13 },
{ name: 'Falco', rating: 13 },
{ name: 'Abby', rating: 12 },
{ name: 'Daisy', rating: 12 },
{ name: 'Elmo', rating: 12 },
]
Os cachorros estão ordenados por classificação, mas dentro de cada classificação, ainda estão ordenados alfabeticamente por nome. Por exemplo, Choco e Ghost têm a mesma pontuação de 14, mas Choco aparece antes de Ghost no resultado da ordenação, porque essa era a ordem no array original.
No entanto, para obter esse resultado, o motor JavaScript não pode usar qualquer algoritmo de ordenação — ele deve ser um chamado “ordenamento estável”. Por muito tempo, a especificação de JavaScript não exigiu estabilidade de ordenação para Array#sort, deixando isso para a implementação. E porque esse comportamento não estava especificado, você também poderia obter este resultado de ordenação, onde Ghost aparece repentinamente antes de Choco:
[
{ name: 'Ghost', rating: 14 }, // 😢
{ name: 'Choco', rating: 14 }, // 😢
{ name: 'Bandit', rating: 13 },
{ name: 'Falco', rating: 13 },
{ name: 'Abby', rating: 12 },
{ name: 'Daisy', rating: 12 },
{ name: 'Elmo', rating: 12 },
]
Em outras palavras, os desenvolvedores de JavaScript não podiam confiar na estabilidade da ordenação. Na prática, a situação era ainda mais irritante, pois alguns motores JavaScript usariam uma ordenação estável para arrays curtos e uma ordenação instável para arrays maiores. Isso era realmente confuso, já que os desenvolvedores testavam seu código, viam um resultado estável, mas então, de repente, obtinham um resultado instável em produção quando o array era um pouco maior.
Mas há boas notícias. Nós projetamos uma alteração na especificação que torna Array#sort estável, e ela foi aceita. Todos os principais motores de JavaScript agora implementam uma ordenação estável em Array#sort. É apenas uma preocupação a menos para os desenvolvedores de JavaScript. Legal!
(Ah, e fizemos o mesmo para TypedArrays: essa ordenação agora também é estável.)
Observação: Embora a estabilidade seja agora exigida pela especificação, os motores de JavaScript ainda são livres para implementar qualquer algoritmo de ordenação que prefiram. V8 usa Timsort, por exemplo. A especificação não exige nenhum algoritmo de ordenação específico.