listas - sort de python
¿Es timsort de propósito general o específico de Python? (6)
El algoritmo es bastante genérico, pero los beneficios son más bien específicos de Python. A diferencia de la mayoría de las rutinas de clasificación, lo que le importa a python''s list (que es lo que usa timsort) es evitar comparaciones innecesarias, porque generalmente las comparaciones son mucho más caras que el intercambio de elementos (que siempre es solo un conjunto de copias de puntero) o incluso la asignación de algunos memoria extra (porque siempre es solo una variedad de punteros, y la sobrecarga es pequeña en comparación con la sobrecarga promedio en cualquier operación de Python).
Si estás bajo restricciones similares, entonces puede ser adecuado. Todavía no he visto ningún otro caso en el que las comparaciones sean realmente tan caras :-)
Timsort es un mergesort adaptativo, estable y natural. Tiene un rendimiento sobrenatural en muchos tipos de matrices ordenadas parcialmente (menos de lg (N!) Comparaciones necesarias, y tan pocas como N-1), pero tan rápido como el anterior híbrido de muestreo altamente sintonizado de Python en matrices aleatorias.
¿Has visto usar timsort fuera de CPython? ¿Tiene sentido?
La descripción que vinculó se ve completamente general.
No parece particularmente familiar, pero los mergesorts "inteligentes" son bastante comunes en el amplio mundo del software.
En cuanto a si tiene sentido, eso depende de lo que esté ordenando, y del costo relativo de las comparaciones frente a la asignación de memoria. Un tipo que requiere hasta 2 * N bytes de memoria extra no será una buena opción en un entorno con memoria limitada.
Respondido ahora en Wikipedia : timsort se usará en Java 7 que lo copió de Android.
Sí, tiene bastante sentido usar timsort fuera de CPython, en específico, o Python, en general.
Actualmente se está realizando un esfuerzo para reemplazar el "tipo de combinación modificado" de Java con timsort, y los resultados iniciales son bastante positivos.
Timsort también se encuentra en Android ahora: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort