Más sobre miMerge.
Al parecer el primer sitio donde aparece un algoritmo similar es un articulo de 1993 que mencionan en el porque Python usa mergesort. Tim lo llama Timsort.
GNU libc también lo usa. Según el autor porque es más eficiente con la jerarquía de caches actual (cuyo mejor caso se asemeja al uso de cintas en los 80).
Aquí lo llaman “adaptive, stable, natural mergesort”. Parece que he llegado 5 años tarde :P.
P.D.: JODER, hasta la idea de usar min(a,b) memoria en la funcion merge es calcada…
Parece que esa versión además cuenta con optimizaciones. El algoritmo simplemente es cojonudo.
P.D.2: Un resumen de la historia. ¿Alguien sabe si Python y Perl lo siguen usando y aún es el algoritmo más rápido de facto?