Substituindo a implementação padrão do JDK (“Mergesort”), escrita por Joshua Bloch, o “timsort” (adaptado pelo mesmo Joshua Bloch a partir da implementação em C usada pelo Python), usado em java.util.Arrays.sort e java.util.Collections.sort, promete ser bem mais rápido para dados já parcialmente ordenados, e conservar o mesmo desempenho para dados aleatórios.
Replace “modified mergesort” in java.util.Arrays.sort with timsort
Visualising Sorting Algorithms: Python’s timsort
Aqui vai o “paper” que define o timsort: http://bugs.python.org/file4451/timsort.txt
Timsort:
Quicksort:
