Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Timsort, the Python sorting algorithm

skerritt.blog

Post reply on HN
Print view View original

41–50 of 135 posts

Re: Timsort, the Python sorting algorithm

#41

Post by hinkley »

anderskaseorg wrote: post #36
hinkley wrote: post #20

Earlier quoted context omitted.

You can’t. Merge sort copies data back and forth between two spaces the size of the data set. That’s O(n) extra space. I spent some time four summers ago with merge sort. I had a PoC for an in-place algorithm that survived several rounds of poorly selected sample data. That was quite a disappointment. In looking around I believe I ran across several implementations that required sqrt(n) extra space and one that I thi…

Algorithms for stable, in-place merging in linear time, hence merge sorting in O(n log n) time, have been known since 1977 ( https://doi.org/10.1137/0206025 ). This first algorithm was too complicated with too large of a constant factor to be practical, but has since been improved.

How many people do you suppose can read that link?

Re: Timsort, the Python sorting algorithm

#42

Post by z0r »

hinkley wrote: post #38
z0r wrote: post #27

Earlier quoted context omitted.

i couldn't find a direct reference, but i remembered that sedgewick's c++ algorithms book had an in-place iterative mergesort with no auxiliary space. that probably was a false memory, but it seems that there is such a beast: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22....

I remember this article now. As someone else said, for certain time complexities there are more algorithms available. I believe when I realized that fixing my bug would turn it essentially into this algorithm, I found something else to do.

I just tried to read this, and not only is it horrifyingly complex it isn't stable, so it doesn't really fit the bill (even if you allow for strange complexities)

Re: Timsort, the Python sorting algorithm

#43

Post by hinkley »

anderskaseorg wrote: post #36
hinkley wrote: post #20

Earlier quoted context omitted.

You can’t. Merge sort copies data back and forth between two spaces the size of the data set. That’s O(n) extra space. I spent some time four summers ago with merge sort. I had a PoC for an in-place algorithm that survived several rounds of poorly selected sample data. That was quite a disappointment. In looking around I believe I ran across several implementations that required sqrt(n) extra space and one that I thi…

Algorithms for stable, in-place merging in linear time, hence merge sorting in O(n log n) time, have been known since 1977 ( https://doi.org/10.1137/0206025 ). This first algorithm was too complicated with too large of a constant factor to be practical, but has since been improved.

It concerns me that the most recent citation in that bibliography says “ We achieve our goal using Recursive Partitioning combined with In Place merging to sort a given array”

Stack frames are external storage. I’d have to see the code to see how they manage to do recursion without log(n) external storage.

Traditional merge sort can be written using iteration, which makes the external storage for sort state O(1), but the semi spaces are still there.

Re: Timsort, the Python sorting algorithm

#44

Post by lemagedurage »

Animats wrote: post #24

You can beat O(n log n). That limit is for sorts that use only a ">" comparison. A distribution sort, where you distribute the keys over buckets, can approach O(n). The first software patent, for SyncSort, is for a sort that beats O(n log n). The basic idea is to read records for a while, get some stats about the key distribution, and set up the buckets to get a roughly equal fraction of the observed keyspace. If blo…

Big O notation is about the theoretical upper bound of an algorithm. Clever data-based tricks like putting items in buckets or gathering statistics are unrelated to this notation as they rely on a certain consistency. Maybe you should call it average run time on typical data.

Re: Timsort, the Python sorting algorithm

#45

Post by eropple »

quickthrower2 wrote: post #39
boltzmannbrain wrote: post #21

"never heard of"?? I would hope all Python devs at some point Google "What algorithm is Python's built-in sort function?"... https://docs.python.org/2/howto/sorting.html#sort-stability-... https://stackoverflow.com/questions/10948920/what-algorithm-...

Great, yet another True-Scotsman of being a proper developer. There is so much you should have read, googled, written to be a "True" dev these days. My theory is - if you are often learning stuff and producing good working code be happy. Not every developer needs to know the underlying sort algorithms.

Understanding where a system breaks is a pretty critical part of "producing good working code," at least for definitions of "good" beyond "closes the bite-sized, cog-in-a-machine story assigned to me in this sprint." I'd hope that any developer making decisions of note in a nontrivial system was at least dimly aware of their language's sort complexity.

Re: Timsort, the Python sorting algorithm

#47

Post by dkersten »

quickthrower2 wrote: post #39
boltzmannbrain wrote: post #21

"never heard of"?? I would hope all Python devs at some point Google "What algorithm is Python's built-in sort function?"... https://docs.python.org/2/howto/sorting.html#sort-stability-... https://stackoverflow.com/questions/10948920/what-algorithm-...

Great, yet another True-Scotsman of being a proper developer. There is so much you should have read, googled, written to be a "True" dev these days. My theory is - if you are often learning stuff and producing good working code be happy. Not every developer needs to know the underlying sort algorithms.

The person never said that you had to google it to be a "proper developer", just that they hoped that every python developer would have done so.

Re: Timsort, the Python sorting algorithm

#49

Post by ziggity »

jonas21 wrote: post #32
ziggity wrote: post #29

Earlier quoted context omitted.

And then 3 years later we have [0] and 6 years after that we have [1]. I appreciate Masters of the Universe types like Bloch and Lea contributing wickedly-efficient code, but somehow it's always mere mortals who end up mopping things up after the fact. Whether it's a bug in the actual algorithm or a "Comparison method violates its general contract!" exception that happens once in a blue moon, I think putting TimSort…

The "Comparison method violates its general contract!" exception is due to a bug in the caller's code, not in the sort implementation. If you have a bug in your code, just because you're able to get away with it today doesn't mean you should expect to get away with it forever.

I agree in theory. But in practice that specific caller's code bug was so widespread and Timsort broke so much existing code that it warranted offering a "-Djava.util.Arrays.useLegacyMergeSort=true" option.

The specific line from the Javadoc you're alluding to [0] is:

> The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y.

The problem is the second implied half of that statement: Pre-Timsort it was ", and if you don't, results might not be sorted in the correct order" while with Timsort it was ", and if you don't, you will get a RuntimeException."

It's way too easy to accidentally violate that condition: System.currentTimeMillis(), incorrect null handling, random numbers. Sometimes not even in the Comparator itself. The condition I posted, plus the other two:

> The implementor must also ensure that the relation is transitive: (x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0.

> Finally, the implementor must ensure that x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.

Are just way too easy for someone to inadvertently violate to justify a RuntimeException when it occurs.

[0] https://docs.oracle.com/javase/7/docs/api/java/lang/Comparab...

Re: Timsort, the Python sorting algorithm

#50

Post by leshow »

ken wrote: post #31

Besides Python and Java, it's also the sorting algorithm used by Chrome, Android, and Swift. At this point I think more than half the world's programmers are using Timsort, whether they realize it or not.

And Rust, the rust std lib uses a modified timsort/mergesort
Post reply on HN