Menu
Timsort is an adaptive, stable, natural mergesort. It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays.
Have you seen timsort used outside of CPython? Does it make sense?
896
Timsort is the default sorting algorithm in Python, Java, and NodeJS.
Timsort is a hybrid, stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language.
It implements the idea that the real-world data sets almost always contain already ordered subsequences, so the sorting strategy is to identify them and sort them further using both merge and insert methods. Timsort is one of the best sorting algorithms in terms of complexity and stability.
Java uses dual-pivot sort for primitives, which is an unstable sort. Java uses timsort, a stable sorting algorithm for objects.
Yes, it makes quite a bit of sense to use timsort outside of CPython, in specific, or Python, in general.
There is currently an effort underway to replace Java's "modified merge sort" with timsort, and the initial results are quite positive.
156
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
