Python · Avançado · Inglês · Técnico
Timsort
Algoritmo de ordenação adaptativo, criado por Tim Peters para o Python, que combina merge sort e insertion sort e aproveita trechos já ordenados. A ordenação é estável.
Onde usar
Explica por que ordenar em duas passadas por chaves diferentes funciona e por que listas quase ordenadas ordenam em tempo próximo do linear. Em code review, justifica ordenar em várias passadas.
Em código
ps = [('Ana', 30), ('Bia', 25), ('Cao', 30)]
ps.sort(key=lambda p: p[0])
ps.sort(key=lambda p: p[1])
print(ps) # Ana antes de Cao (estável)Exemplos
Timsort is stable, so sorting twice works.
O Timsort é estável, então ordenar duas vezes funciona.
Nearly sorted lists are very fast with Timsort.
Listas quase ordenadas são muito rápidas com Timsort.
Cuidado
Não presuma que a estabilidade vale em qualquer linguagem; no Python ela é garantida pela documentação de sort e sorted.
Origem
Nome em homenagem a Tim Peters, que o criou em 2002 para o Python.