4 ms·
How does TimSort improve (if at all) on what is published on the topic in academia?
by amichail 17y ago
How does TimSort improve (if at all) on what is published on the topic in academia?
- mbrubeck 17y agoHere's another link to the documentation (since svn.python.org is not responding for me): http://bugs.python.org/file4451/timsort.txt 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.
- amichail 17y agoAdaptive sorting has been studied in academia: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8017 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8...
- akeefer 17y agoAcademic work on subjects like sorting tends to focus more on things like big-O runtimes and less on implementation details that lead to reducing the various constants that big-O simplifies out, or that arise from real-world data patterns rather than totally randomized or idealized data.