Hacker News new | past | comments | ask | show | jobs | submit login

Here's another link to the documentation (since svn.python.org is not responding for me): http://bugs.python.org/file4451/timsort.txt

TimSort is essentially merge sort plus optimizations. The major optimization is that it identifies already-sorted subsequences within the input, and sorts these "runs" plus some surrounding elements using a fast binary insertion sort. This means that for input that isn't completely random, it doesn't need to do as many comparisons as a pure mergesort. TimSort has also been tuned based on empirical testing on real-world data/hardware.




Adaptive sorting has been studied in academia:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8...




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: