Among the previous discussions of timsort:<p><a href="https://news.ycombinator.com/item?id=21196555" rel="nofollow">https://news.ycombinator.com/item?id=21196555</a><p><a href="https://news.ycombinator.com/item?id=17436591" rel="nofollow">https://news.ycombinator.com/item?id=17436591</a><p><a href="https://news.ycombinator.com/item?id=17436591" rel="nofollow">https://news.ycombinator.com/item?id=17436591</a>
Interestingly, Timsort used to be broken [1]. They found that by trying to prove correctness. I recall Stijn de Gouw remarking that they wanted to have their proof artefact evaluated, but you'd need a seriously beefy machine to do so.<p>[1] <a href="http://www.envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/" rel="nofollow">http://www.envisage-project.eu/proving-android-java-and-pyth...</a>
Closely related is pattern defeating quicksort ( <a href="https://github.com/orlp/pdqsort" rel="nofollow">https://github.com/orlp/pdqsort</a> ), which adapts quicksort to take advantage of sorted runs. I've adapted a few quicksorts to pdqsort and seen good speedups (as people were often sorting partially sorted data)<p>Basically: Timsort is to mergesort as pdqsort is to quicksort
I thought it was widely known, IIRC a number of languages have adopted it as the stdlib default sorting algorithm for either unstable/stable sort (can't remember which is it?)<p>I'm not big into algorithms but I believe that pdqsort and timsort were supposed to be the best two general sorts.
Here [1] is a great (short, readable) paper from 2015 that explains Timsort and similar stack-merge sorting algorithms. It also gives a runtime analysis, and a simplified version of the algorithm that they call 'alpha-sort'.<p>[1] <a href="https://hal-upec-upem.archives-ouvertes.fr/hal-01212839/file/merge_strategies.pdf" rel="nofollow">https://hal-upec-upem.archives-ouvertes.fr/hal-01212839/file...</a>
Whenever there's a discussion about sorting I like to put in a little reminder about the humble Radix Sort which is often overlooked by academics because it's so simple. It deserves more attention as it is super fast: O(kn). Academics disregard it because it won't sort floating point numbers, but the vast majority of real-world use cases deal with alphanumerics, so Radix Sort should get more press than it does.
Also interesting is pdqsort, which will become Go's standard sort.<p><a href="https://news.ycombinator.com/item?id=31106157" rel="nofollow">https://news.ycombinator.com/item?id=31106157</a><p><a href="https://news.ycombinator.com/item?id=31098822" rel="nofollow">https://news.ycombinator.com/item?id=31098822</a>
9 lines of Timsort was the centerpiece of the Oracle-Google Android Java lawsuit.<p><a href="https://www.infoq.com/news/2012/05/nine-lines/" rel="nofollow">https://www.infoq.com/news/2012/05/nine-lines/</a>
> built for the real world — not constructed in academia.<p>Why would lacking in evidence and rigor be considered a plus?<p>Does Timsort pride itself of being the homeopathy of sorting algorithms?<p>What a bizzare brag to make.
It's well known.<p>Nevertheless, the article was good.<p>If the author is reading this, consider dropping the "you've never heard of" from the title; you don't want to assume things about your reader.
This blog steals content from other sites, original is at <a href="https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399" rel="nofollow">https://hackernoon.com/timsort-the-fastest-sorting-algorithm...</a>.<p>Unfortunately I cannot downvote.<p>Please don't link plagiarized content. This guy also linked to his own "Big O Notation" in his page, where he says O(n) is polynomial<p>>>>In our shopping list example, in the worst-case of our algorithm it prints out every item in the list sequentially. Since there are n items in the list, it takes O(n) polynomial time to complete the algorithm.