Timsort
De Wikipedia, a enciclopédia encyclopedia
Timsort é um algoritmo de ordenação híbrido derivado do merge sort e do insertion sort, projetado para ter boa performance em vários tipos de dados do mundo real. Foi inventado por Tim Peters em 2002 para ser usado na linguagem de programação Python, e tem sido o algoritmo de ordenação padrão de Python desde a versão 2.3. Ele atualmente é usado para ordenar arrays em Java SE 7.[1]
Tim Peters descreve o algoritmo da seguinte forma[2]:
[...]um adaptativo, estável, merge sort natural, modestamente chamado de timsort (hey, eu mereço <wink>). Tem desempenho sobrenatural em muitos tipos de arrays parcialmente ordenados (menos de lg(N!) comparações necessárias, e tão poucas quanto N-1), no entanto, tão rápido quanto o algoritmo anterior altamente sintonizado, híbrido, samplesort de Python em matrizes aleatórias. Em suma, a rotina principal passa sobre a matriz uma vez, da esquerda para a direita, alternadamente, identificando o próximo passo, em seguida, fundindo-os em passos anteriores "inteligentemente". Todo o resto é complicação pela velocidade, e alguma medida duramente conquistada da eficiência de memória.
Como o merge sort, é um algoritmo de ordenação por comparação estável com uma complexidade de pior caso de .[3]
De acordo com a teoria da Informação, nenhuma ordenação por comparação pode executar em menos de , no caso médio, o que exige que a ordenação por comparação tome um tempo de em dados aleatórios. No entanto, em dados do mundo real, o Timsort muitas vezes exige muito menos do que , porque ele tira vantagem do fato de que sublistas dos dados podem já estar em ordem ou ordem inversa.[4]