Adaptive mergesort tambien puede ser mejorado.
En este documento, explican como mediante una desordenación aleatoria de los elementos del vector a ordenar, los algoritmos adaptativos de ordenación son más rápidos.
Es un punto de vista probabilistico, y supongo que presupone que el vector a ordenar no está inicialmente desordenado de forma realmente aleatoría.
De todas formas, un mergesort adaptativo no es la panacea. Su gran virtud es poder usarlo en cualquier caso con una gran eficacia. Por ejemplo si alguien “se equivoca” y decide ordenar un vector ya ordenado, o un vector que contiene ya un vector ordenado. Quicksort es mucho más facíl de implementar, pero más lento (y no sólo en estos casos).
P.D.: El algoritmo en el que aplican esta mejora no es “Timsort”, sino uno de sus predecesores.
P.D.2:Algún día acabaré mi versión de Timsort… más tarde haré algo mejor :p.