Estabilidade de ordenação: o que garante e quando importa

O que é

Uma ordenação é estável quando os elementos que se comparam como iguais mantêm a sua ordem relativa de entrada. O HOWTO de ordenação do Python afirma que as suas ordenações têm estabilidade garantida. A MDN indica que, desde o ECMAScript 2019, a especificação exige que Array.prototype.sort seja estável. O pacote sort de Go documenta que Stable mantém a ordem original dos elementos iguais, ao contrário de Sort, que não garante estabilidade. O sort do GNU tem a opção --stable, que desativa a comparação de último recurso sobre a linha inteira. A estabilidade é uma propriedade do algoritmo: merge sort, insertion sort e Timsort são estáveis; um quicksort simples ou um heapsort não são.

Por que importa

A estabilidade permite compor ordenações. Ordenar por data e depois, de forma estável, por estado produz linhas agrupadas por estado, com as datas em ordem dentro de cada grupo. Numa tabela ordenável que reordena a cada clique, os empates mantêm a ordem anterior em vez de serem embaralhados. O caso oposto é o SQL: ORDER BY sobre uma coluna não única não promete nada sobre os empates, por isso resultados paginados podem mostrar uma linha duas vezes ou nunca, a menos que se acrescente uma coluna única como critério de desempate.

Como aplicar

• Em ordenações por várias chaves, prefira uma única chave composta (key=lambda r: (r.status, r.date)): é feita numa só passagem e a intenção fica evidente. A alternativa, quando as chaves precisam de direções diferentes, é aplicar ordenações estáveis sucessivas, da chave menos significativa para a mais significativa.
• Em SQL, termine todo ORDER BY usado para paginação com uma coluna única (ORDER BY created_at, id).
• Confie na estabilidade apenas onde a documentação a declara; procure essa palavra na referência da biblioteca antes de depender dela.
• O reverse=True do Python mantém os elementos iguais na sua ordem original, o que difere de ordenar e depois inverter a lista.
• Na linha de comando, adicione -s ao sort do GNU quando os empates tiverem de manter a ordem do arquivo, por exemplo ao ordenar um log por um único campo.

Armadilhas

Testes que comparam uma saída ordenada com empates dependem tanto da estabilidade quanto da ordem de entrada; use dados esperados sem empates ou ordene com uma chave completa. A collation do locale (LC_ALL) altera a ordem da mesma entrada entre máquinas, por isso fixe o locale nos scripts. Algoritmos estáveis podem precisar de memória adicional (buffers de merge), o que pesa em arrays muito grandes na memória. A estabilidade nada diz sobre a consistência da função de comparação: um comparador inconsistente produz ordem indefinida em qualquer algoritmo.