32
votes

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?

7
why do you ask? without more context, your question cannot be answered. - user3850
Have you noticed "Have you seen timsort used outside of CPython?" part? - Constantin
i have noticed it, and it still gives us no context. what would you learn from a simple "no" as answer? - user3850
'timsort' is really very specific, although it won't mean much to you unless you actually know what timsort is. - Thomas Wouters

7 Answers

31
votes

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.

23
votes

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 :-)

6
votes

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.

4
votes

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

0
votes

The description you linked looks completely general.

0
votes

Timsort is not Python-specific. The benefits of using Timsort in Python to sort a list of object references exists in any programming language which has pointers or object references. For instance, Java SE 7+, Android and Swift use Timsort to sort objects.

On the other hand, some variation of quicksort (eg introsort, dual-pivot quicksort) usually sorts primitive types faster, due to cache coherence, and therefore it is usually chosen for this task.