Grokking Timsort

Question

Hay un tipo (relativamente) nuevo en el bloque llamado Timsort. Se ha utilizado como list.sort de Python, y ahora va a ser the new Array.sort in Java 7.

Hay some documentation y una tiny Wikipedia article describir las propiedades de alto nivel de la clase y algunas evaluaciones de desempeño de bajo nivel, pero tenía curiosidad por si alguien puede proporcionar algo de pseudocódigo para ilustrar lo que Timsort está haciendo, exactamente, y lo que son la clave cosas que hacen que sea zippy. (Esp. En relación con el documento citado, "Optimista Clasificación e información teórica complejidad.")

(Véase también related StackOverflow post.)

Answer 1

Citando la parte pertinente de una entrada en el blog ahora eliminado: Visualising Sorting Algorithms: Python's timsort

El negocio de fin de timsort es un mergesort que funciona en las carreras de elementos pre-ordenados. Se elige un minrun de longitud mínima de ejecución para garantizar que las fusiones finales estén lo más equilibradas posible: para 64 elementos, el minrun pasa a ser 32.Antes de que comiencen las fusiones, se realiza una única pasada a través de los datos para detectar ejecuciones preexistentes de elementos ordenados. Las carreras descendentes se manejan simplemente invirtiéndolas en su lugar. Si la longitud de ejecución resultante es menor que minrun, se aumenta a minrun usando sorting de inserción. En una matriz mezclada sin ejecuciones preexistentes significativas, este proceso se ve exactamente como lo hemos supuesto anteriormente: ordenando previamente bloques de elementos minrun utilizando la ordenación por inserción, antes de fusionarlos con la clasificación por fusión.

[...]

• timsort encuentra una carrera descendente, e invierte la carrera en el lugar. Esto se hace directamente en la matriz de punteros, por lo que parece "instantáneo" desde nuestro punto de vista.
• La ejecución se ha aumentado a minrun de longitud mediante la ordenación por inserción.
• No se ha detectado ninguna carrera al comienzo del siguiente bloque, y la ordenación por inserción se usa para ordenar todo el bloque. Tenga en cuenta que los elementos ordenados en la parte inferior de este bloque no se tratan de manera especial: timsort no detecta las ejecuciones que se inician en el medio de los bloques que se amplifican a minrun.
• Finalmente, mergesort se usa para fusionar las ejecuciones.

Answer 2

Este cambio fue a través de la core-libs mailing list cuando entró en lo que existe cierta discusión y enlaces útiles allí. Aquí está el web rev con cambios en la revisión del código y también el original patch.

Los comentarios en el código dicen: Nota

Implementación: Esta aplicación es un producto estable, adaptable,
mergesort iterativo que requiere mucho menos que n lg (n) comparaciones
cuando la matriz de entrada es parcialmente ordenado, mientras ofrece el rendimiento
de un mergesort tradicional cuando el conjunto de entrada es
ordenado al azar. Si la matriz de entrada está casi ordenada, la implementación
requiere aproximadamente n comparaciones.
Los requisitos de almacenamiento temporal varían desde una pequeña constante para los arreglos de entrada
casi 0/2 a referencias de objeto para la entrada ordenada aleatoriamente
matrices.

La implementación toma igual ventaja de ascendente y
orden descendente en su matriz de entrada, y puede tomar ventaja de
orden ascendente y descendente en diferentes partes del mismo matriz de entrada
. Es adecuado para fusionar dos o más matrices ordenadas:
simplemente concatenar las matrices y ordenar la matriz resultante.
La implementación fue adaptada del tipo de lista de Tim Peters para Python
TimSort. Utiliza Techiques de Peter McIlroy "Optimista
Clasificación e información teórica Complejidad", en Actas de la
Cuarto Simposio Anual ACM-SIAM en discreto Algoritmos, pp 467-474,
de enero de 1993.

Buried ahí está el very useful link to the Python implementation details, y creo que es un gran lugar para comenzar, seguido por el código. Para ser un nivel increíblemente alto, timsort mejora el rendimiento al detectar ejecuciones de datos clasificados y aprovechar esa estructura durante el proceso de clasificación.