Timsort

Timsort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	$\Theta(n\log n)$
complexidade caso médio	$\Theta(n\log n)$
complexidade melhor caso	$\Theta(n)$
complexidade de espaços pior caso	$\Theta(n)$
estabilidade	estável
data	2002
Algoritmos

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.

Tim Peters descreve o algoritmo da seguinte forma :

[...]um adaptativo, estável, merge sort natural, modestamente chamado de timsort (hey, eu ganhei ele <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 $\Theta(n \log n)$.

De acordo com a teoria da Informação, nenhuma ordenação por comparação pode executar em menos de $\log_2(n!)$, no caso médio, o que exige que a ordenação por comparação tome um tempo de $\Omega(n \log n)$ em dados aleatórios. No entanto, em dados do mundo real, o Timsort muitas vezes exige muito menos do que $\log_2(n!)$, porque ele tira vantagem do fato de que sublistas dos dados podem já estar em ordem ou ordem inversa.

Ver também

• Merge sort
• Insertion sort
• Algoritmos de ordenação

Ligações externas

• Visualising Timsort - a fonte para a imagem desta página.