Por que sort(() => Math.random() - 0.5) não embaralha a lista

A ordem mais provável é não embaralhar nada

Em 18,79% das rodadas — quase 1 em cada 5 —, o sort(() => Math.random() - 0.5) devolve a lista exatamente como ela entrou. Em 17,17%, devolve ela de trás para frente. Juntas, essas duas ordens — que são as duas MENOS aleatórias que uma lista de 4 itens pode assumir — respondem por mais de 1 em cada 3 resultados, contra os 8,33% que um sorteio justo daria para qualquer par de ordens.

O qui-quadrado contra a distribuição uniforme, em 23 graus de liberdade, sai 1.158.685 para o comparador aleatório. O valor crítico usual, a 5%, é aproximadamente 35. O Fisher-Yates da ferramenta sai em 16,04 — dentro da faixa que um sorteio justo produz por flutuação normal de amostragem.

Por que isso acontece: o sort não sabe que o comparador é aleatório

Array.prototype.sort não embaralha — ele ORDENA, e confia que o comparador descreve uma ordem que já existe. A especificação do ECMAScript chama isso de consistent comparator (comparador consistente) e exige, no texto normativo da seção que define SortIndexedProperties, entre outras condições: “Calling comparator(a, b) always returns the same value v when given a specific pair of values a and b as its two arguments.” — ou seja, chamar o mesmo par duas vezes tem que devolver o mesmo resultado. Um comparador que sorteia de novo a cada chamada quebra essa exigência na primeira vez que compara o mesmo par duas vezes.

E a especificação já avisa o que acontece quando isso falha: “The sort order is implementation-defined if sortCompare is not a consistent comparator for the elements of items.” — a ordem de saída fica por conta de cada implementação. Não é erro, não lança exceção: é comportamento não especificado, de propósito, porque garantir uma ordem para um comparador inconsistente exigiria da especificação decidir o que “ordenar” significa quando não existe ordem nenhuma para achar. O blog oficial do V8 descreve o mesmo requisito em linguagem direta: um comparador que não segue o padrão consistente é inconsistent e “can have arbitrary side-effects”.

Isso explica o “implementation-defined”, mas não explica por que o defeito tem a CARA que tem — por que “original” e “invertida” saem na frente, e não duas ordens quaisquer. A resposta está no algoritmo por trás do sort: para uma lista de 4 itens, tanto o V8 antigo (Quicksort com fallback para Insertion Sort abaixo de 10 elementos) quanto o V8 atual (Timsort, que só entra em Insertion Sort quando não encontra uma sequência já ordenada de pelo menos 32 a 64 elementos) caem no mesmo lugar: Insertion Sort. E Insertion Sort processa a lista da esquerda para a direita, comparando cada item contra o que já foi organizado antes dele — poucas comparações, muita chance de nenhuma delas discordar o bastante da ordem original (ou discordar sempre, na direção oposta) para embaralhar de verdade.

A prova de que é o algoritmo, não a sorte do gerador

Um jeito de descartar “foi coincidência da semente” é rodar sem semente nenhuma — com o Math.random() de verdade do motor. Fizemos isso à parte, fora do build (esta conta não é reproduzível e por isso não está travada em teste): em 1.000.000 rodadas com o gerador real do Node, a ordem original saiu 18,69% das vezes e a invertida 17,23% — praticamente os mesmos 18,79% e 17,17% que a versão com semente publica aqui. O viés não muda com a fonte de acaso porque ele não mora nela.

A segunda prova está em 6 itens, para cruzar com um número que a própria ferramenta já publicava, medido com o motor de verdade: 29,6% de chance de o primeiro item permanecer em primeiro lugar no Chrome 151, 28,4% no Node 24, contra os 16,7% de um sorteio justo. Medindo de novo aqui, com semente e sem depender de navegador nenhum: 28,64% — a mesma ordem de grandeza. O Fisher-Yates, na mesma conferência, saiu em 16,64%, contra os 16,67% esperados.

Pontos fixos: a conta que não devia depender do tamanho da lista

Para qualquer lista embaralhada de verdade — de 4 itens ou de 6 —, o número esperado de itens que permanecem na MESMA posição é sempre exatamente 1, não importa o tamanho da lista. É a mesma conta que o campo “continuaram no lugar” da ferramenta mostra na tela depois de cada sorteio, olhada em 1.000.000 rodadas em vez de uma. O Fisher-Yates bate nisso: 0,9985 em média. O comparador aleatório, não: 1,3455 — quase 35% a mais de itens parados do que um sorteio justo deixaria.

O conserto não é ajustar o comparador — é trocar de algoritmo

Não existe correção que mantenha .sort() e conserte o viés: o problema não é a FORMA do comparador, é usar um algoritmo de ORDENAR para fazer um SORTEIO. Fisher-Yates (a versão de Durstenfeld, de 1964, que é a que se programa: percorrer a lista de trás para frente e trocar cada posição por uma sorteada entre as que ainda não foram fixadas) não ordena nada — troca de lugar uma vez cada posição, com a probabilidade certa para cada uma, e é matematicamente garantido que as 24 ordens de uma lista de 4 — ou as 720 de uma lista de 6, ou o fatorial do tamanho, para qualquer lista — saiam com a mesma chance. A ferramenta daqui usa esse algoritmo, com a opção de rodar com semente para quem precisa provar o sorteio depois.