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

21–30 of 135 posts

Re: Timsort, the Python sorting algorithm

#22

Post by billforsternz »

kbd wrote: post #7
saagarjha wrote: post #2

Note that Timsort uses O(n) extra space: sometimes this can be undesirable.

Note that this is true for any (edit: stable, nlogn) merge sort.

Heapsort is a lovely, simple, O(NlogN) sort that sorts in place (so that it requires no extra space). (Explicitly stating something that is implied by an existing response).

Edit: Whoops, apparently heapsort is not "stable" (not sure what that means actually), sorry.

Re: Timsort, the Python sorting algorithm

#23

Post by srgpqt »

billforsternz wrote: post #22
kbd wrote: post #7

Earlier quoted context omitted.

Note that this is true for any (edit: stable, nlogn) merge sort.

Heapsort is a lovely, simple, O(NlogN) sort that sorts in place (so that it requires no extra space). (Explicitly stating something that is implied by an existing response). Edit: Whoops, apparently heapsort is not "stable" (not sure what that means actually), sorry.

Stable sort means that the order of same elements is preserved. For example, sorting strings by length, strings of the same length would retain the same order between themselves as they had before sorting.

Re: Timsort, the Python sorting algorithm

#24

Post by Animats »

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 blocks of records show up with very different stats, action has to be taken to adjust the bucketing.

Re: Timsort, the Python sorting algorithm

#26

Post by stefan_ »

ignoramous wrote: post #18

My favourite TimSort story is of ex-Sun employee, Joshua Bloch of Effective Java fame. J Bloch was in audience at the time when Tim Peters presented his new algorithm to sort a list, and he was so blown away that he started porting Tim's implementation right there with an intent to commit it to the JDK mainline [0], which he eventually did [1]. [0] Some of the core JDK developers are really on another level. The JDK…

Then, many years later, input was found that made the Java version crash:

https://link.springer.com/chapter/10.1007/978-3-319-21690-4_...

Re: Timsort, the Python sorting algorithm

#27

Post by z0r »

hinkley wrote: post #20
CraneWorm wrote: post #9

Earlier quoted context omitted.

you can do merge sort in place

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…

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....

Re: Timsort, the Python sorting algorithm

#28

Post by westurner »

Here are the Python 3 docs for sorting [1], in-place list.sort() [2], and sorted() [3] (which makes a sorted copy of the references). And the Timsort Wikipedia page [4].

[1] https://docs.python.org/3/howto/sorting.html#sort-stability-...

[2] https://docs.python.org/3/library/stdtypes.html#list.sort

[3] https://docs.python.org/3/library/functions.html#sorted

[4] https://en.wikipedia.org/wiki/Timsort

Re: Timsort, the Python sorting algorithm

#29

Post by ziggity »

ignoramous wrote: post #18

My favourite TimSort story is of ex-Sun employee, Joshua Bloch of Effective Java fame. J Bloch was in audience at the time when Tim Peters presented his new algorithm to sort a list, and he was so blown away that he started porting Tim's implementation right there with an intent to commit it to the JDK mainline [0], which he eventually did [1]. [0] Some of the core JDK developers are really on another level. The JDK…

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 in Java was a mistake.

[0] https://dertompson.com/2012/11/23/sort-algorithm-changes-in-...

[1] https://bugs.openjdk.java.net/browse/JDK-8203864

Re: Timsort, the Python sorting algorithm

#30

Post by shiblukhan »

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-...

If you want to master how Timsort works and get a feel for it, I highly suggest you try to implement it yourself!

This article is based on Tim Peters’ original introduction to Timsort, found here.

Post reply on HN