Is timsort general-purpose or Python-specific?

Question

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?

Answer 1

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.

Answer 2

The algorithm is pretty generic, but the benefits are rather Python-specific. Unlike most sorting routines, what Python's list.sort (which is what uses timsort) cares about is avoiding unnecessary comparisons, because generally comparisons are a lot more expensive than swapping items (which is always just a set of pointer copies) or even allocating some extra memory (because it's always just an array of pointers, and the overhead is small compared to the average overhead in any Python operation.)

If you're under similar constraints, then it may be suitable. I've yet to see any other case where comparisons are really that expensive, though :-)

Answer 3

It doesn't look particularly familiar, but "smart" mergesorts are pretty common out in the wide world of software.

As for whether it makes sense, that depends on what you're sorting, and the relative cost of comparisons vs. memory allocation. A sort that requires up to 2*N bytes of extra memory isn't going to be a good choice in a memory-constrained environment.

Answer 4

Answered now on Wikipedia: timsort will be used in Java 7 who copied it from Android.

Answer 5

Timsort is also in Android now: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort

Answer 6

The description you linked looks completely general.