Timsort

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 Θ ( n log ⁡ n ) {\displaystyle \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 ! ) {\displaystyle \log _{2}(n!)} , no caso médio, o que exige que a ordenação por comparação tome um tempo de Ω ( n log ⁡ n ) {\displaystyle \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 ! ) {\displaystyle \log _{2}(n!)} , porque ele tira vantagem do fato de que sublistas dos dados podem já estar em ordem ou ordem inversa. TimSort é um algoritmo híbrido de ordenação baseado no MergeSort e InsertionSort. O algoritmo baseia-se na ideia de que, no mundo real, um vetor de dados a ser ordenado contém sub-vetores já ordenados, não importando como (decrescentemente ou crescentemente). Assim, o TimSort está à frente da maioria dos algoritmos de ordenação, mesmo não apresentando descobertas matemáticas complexas. O fato é que na realidade o TimSort não é um algoritmo autônomo, mas um híbrido, uma combinação eficiente de outros algoritmos, temperado com as idéias do autor.