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.
Timsort, the Python sorting algorithm
31–40 of 135 posts
Re: Timsort, the Python sorting algorithm
#32My 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…
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.
Re: Timsort, the Python sorting algorithm
#33My 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…
This looks effective. I will try it out and thanks for posting.
Re: Timsort, the Python sorting algorithm
#34You 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…
> 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
Hadoop Terasort does the same thing of sort, which is to start off with a partitioner doing a radix sort & then sort each part with a lower O number of comparisons (the Spark one actually does local sorts and then has the merge-sort part just fetch ranges after first pass), however those two work great when the key ranges are almost entirely unique with no big runs of identical keys and differing values.
The Timsort one however has an advantage when there are huge runs of identical values or almost sorted inputs, like when you have a time-series with the occasional out of order packet. The galloping mode in the algorithm neatly eats those ranges up very fast.
My favourite example to show sorting is data dependent is the tricolor sort example[1], which illustrates what happens when you have a large number of identical keys.
[1] - https://en.wikipedia.org/wiki/Dutch_national_flag_problem#Th...
Re: Timsort, the Python sorting algorithm
#35Earlier 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.
A "stable" sorting algorithm preserves the relative order of elements with "equal value". This doesn't really apply if you are only sorting simple values, as there is no difference between a 7 and another 7, but does if you are sorted more complicated objects by some key.
Example: sorting 2#a, 1#c, 2#b by only the first number.
An algorithm that produces 1#c, 2#b, 2#a is a correct sorting algorithm, but not stable as it changes the order of 2#a and 2#b.
Re: Timsort, the Python sorting algorithm
#36Earlier 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…
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.
Re: Timsort, the Python sorting algorithm
#37I also love pdqsort. It has many of the same advantages, and has the advantage of being easier to implement (particularly if you already have a quicksort lying around).
https://github.com/orlp/pdqsort
Basically, timsort is to mergesort as pdqsort is to quicksort.
Re: Timsort, the Python sorting algorithm
#38Earlier 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…
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.
Re: Timsort, the Python sorting algorithm
#39"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.
Re: Timsort, the Python sorting algorithm
#40I always thought this sort visualizer was cool http://sorting.at/