Timsort
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:

Como o merge sort, é um algoritmo de ordenação por comparação estável com uma complexidade de pior caso de formula_1.

De acordo com a teoria da Informação, nenhuma ordenação por comparação pode executar em menos de formula_2, no caso médio, o que exige que a ordenação por comparação tome um tempo de formula_3 em dados aleatórios. No entanto, em dados do mundo real, o Timsort muitas vezes exige muito menos do que formula_2, porque ele tira vantagem do fato de que sublistas dos dados podem já estar em ordem ou ordem inversa.
Q181593
algoritmo de ordenação
Concept
Q189057
merge sort
Concept
Q117241
insertion sort
Concept
Q28865
Python
MEDIA
Q186152
array
Concept
Q251
Java SE 7
Concept
Q189057
merge sort
Concept
Q2632949
ordenação por comparação
Concept
Q131222
teoria da Informação
Concept
Q2632949
ordenação por comparação
Concept
Q942403
Timsort
Concept
Q942403
Timsort
Concept
+2002^^http://www.w3.org/2001/XMLSchema#decimal
2002
NUMBER
+2.3^^http://www.w3.org/2001/XMLSchema#decimal
2.3
NUMBER
+7^^http://www.w3.org/2001/XMLSchema#decimal
7
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
instance of
based on
based on
used by
used by
based on
instance of
instance of
subclass of
instance of
instance of