13 ms·

Timsort, the Python sorting algorithm

saagarjha 7y ago
Note that Timsort uses O(n) extra space: sometimes this can be undesirable.
- kbd 7y ago
  Note that this is true for any (edit: stable, nlogn) merge sort.
  - ThreeFx 7y ago
    Not true in general, however IIRC it is the case if you want optimal (i.e. n log n) time complexity.
    - beagle3 7y ago
      Not even in that case. Heapsort guarantees worst case n log n, and so does quicksort if you use an O(n) median selecting algorithm. Stable sorts often do require that, (mergesort is usually stabble, heapsort and quicksort are inherently not), but even that's not required - there is a completely in-place variant of merge sort that only requires O(log n) space for stack (like quicksort; heapsort is O(1)). See e.g. https://xinok.wordpress.com/2014/08/17/in-place-merge-sort-demystified-2/ https://xinok.wordpress.com/2014/08/17/in-place-merge-sort-d...
      - saagarjha 7y ago
        Apparently there is a O(n log n) time, O(1) space, stable sort: https://en.wikipedia.org/wiki/Block_sort https://en.wikipedia.org/wiki/Block_sort
  - CraneWorm 7y ago
    you can do merge sort in place
    - hinkley 7y ago
      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 think claimed log n but was so complicated I never did figure out why it was supposed to work. At least one of these had higher time complexity, but often enough you need to work with data sets that dominate your memory footprint. Even a second array of pointers might push you over.
      - z0r 7y ago
        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.5514&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22....
        hinkley 7y ago
        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.
        z0r 7y ago
        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)
  - billforsternz 7y ago
    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.
    - srgpqt 7y ago
      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.
      - billforsternz 7y ago
        Thanks for the explanation, makes sense. I was tempted to classify this as "irrelevant to me", but then I remembered an application I had recently where I had values (chess games) that I was sorting which I didn't want to reorder if they were adjacent (as far as the sort was concerned) but not identical. Ended up adding an "original order" field as a sort tiebreaker. As it happens a stable sort would have saved me the pain.
    - cdirkx 7y ago
      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.
      - billforsternz 7y ago
        Thanks for the explanation, interesting.
    - hinkley 7y ago
      Said another way, if I sort my database by user names, the John Smith who has been my customer the longest always comes first in the line of John Smiths. One of the things you can do with a stable sort is to fake complex sorting by iteratively sorting by each criteria. Though I have rarely seen that be practical anywhere other than tabular data.
  - kragen 7y ago
    Interestingly, the Golang standard library has a sort in it that claims to be a stable in-place O(N log N) mergesort.
yagibear 7y ago
Never heard of since it was last discussed on HN: https://news.ycombinator.com/item?id=17436591 https://news.ycombinator.com/item?id=17436591
- dang 7y ago
  And https://news.ycombinator.com/item?id=17883461 https://news.ycombinator.com/item?id=17883461 after that. Quite a few submissions for something no one has heard of: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=Timsort&sort=byDate&type=story https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... The other main discussions are 2011: https://news.ycombinator.com/item?id=3214527 https://news.ycombinator.com/item?id=3214527 2009: https://news.ycombinator.com/item?id=752677 https://news.ycombinator.com/item?id=752677
Beldin 7y ago
I heard of it from a talk about a bug in the implementation of TimSort in several popular libraries [1]. That bug should be fixed in Java, Android and Python. If you're using another language, you might want to verify that the bug is fixed/not present in your library [1] http://www.envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ http://www.envisage-project.eu/proving-android-java-and-pyth...
timothycrosley 7y ago
As an (unrelated to the Algorithm) Python developer, also named Tim, I've never been able to hear the last of it. Still a great algorithm, though!
pwinnski 7y ago
I think most Python devs have heard of this, as well as avid followers of HN, of course.
Congeec 7y ago
There are cases where pattern defeating sort beats timsort https://github.com/EmuraDaisuke/SortingAlgorithm.HayateShiki https://github.com/EmuraDaisuke/SortingAlgorithm.HayateShiki
- purplezooey 7y ago
  "external area" tho
pitaj 7y ago
Rust uses timsort as the stable sorting algorithm in its standard library. https://doc.rust-lang.org/std/primitive.slice.html#method.sort https://doc.rust-lang.org/std/primitive.slice.html#method.so...
tsegratis 7y ago
WikiSort should even be faster still Original author: https://github.com/BonzaiThePenguin/WikiSort https://github.com/BonzaiThePenguin/WikiSort Graph and copyage (by me): https://tse.gratis/aArray/#details https://tse.gratis/aArray/#details Or grail sort: https://github.com/Mrrl/GrailSort/blob/master/README.md https://github.com/Mrrl/GrailSort/blob/master/README.md Sort, is a deep rabbit hole
- tsegratis 7y ago
  WikiSort previous discussion https://news.ycombinator.com/item?id=7404223 https://news.ycombinator.com/item?id=7404223 Can't find a direct comparison with TimSort though..
james_s_tayler 7y ago
Heard about it by reading Java stacktraces one day.
fghorow 7y ago
Tim Peters is also the IEEE-754 guru for the Python codebase. Truly a giant of the Python community. <1/2 wink-ly yr's>
ignoramous 7y ago
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 code, post 1.5, is a joy to read, though verbose. Compilers and Languages seems to attract a certain caliber of engineers, I think. [1] https://bugs.openjdk.java.net/browse/JDK-6804124 https://bugs.openjdk.java.net/browse/JDK-6804124
- stefan_ 7y ago
  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_16 https://link.springer.com/chapter/10.1007/978-3-319-21690-4_...
  - kevingadd 7y ago
    I found a similar problem using a fairly battle-tested C# implementation of timsort. Felt lucky that I had managed to reproduce it in a dev environment instead of it being a mysterious crash for users.
    - lqet 7y ago
      Many years ago, I copied an implementation of the Cohen-Sutherland algorithm (for line clipping) to C++ from pseudo code (I don't remember where I got this pseudo code from, but other sources used equivalent pseudo code). The code (it was a backend server code for a web app) was heavily tested with ab [0] and JMeter [1] against extreme load, everything seemed to worked fine. Fast-forward 6 months, when we had a sudden peak in users (for a few days, we went from around 500 visitors a day to around 500.000, which roughly meant > 5 million requests per day). Suddenly, the backend, which ran without problems for half a year, crashed in production every 5 hours or so with a segmentation fault. I could not for the life of me reproduce this. After some panicking, I let the backend run in gdb in production against the ~50 requests per second we were still getting. After a few hours, the segfault occurred again, and I figured out that on extremely rare edge cases, the pseudo code I copied to C++ divided by 0, which lead to chain of problems afterwards, eventually resulting in said segfault. If I remember correctly, the fix was trivial. [0] https://httpd.apache.org/docs/2.4/programs/ab.html https://httpd.apache.org/docs/2.4/programs/ab.html [1] https://jmeter.apache.org/ https://jmeter.apache.org/
mharrison 7y ago
Tim the enchanter!
boltzmannbrain 7y ago
"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-and-complex-sorts https://docs.python.org/2/howto/sorting.html#sort-stability-... https://stackoverflow.com/questions/10948920/what-algorithm-does-pythons-sorted-use https://stackoverflow.com/questions/10948920/what-algorithm-...
- shiblukhan 7y ago
  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.
- quickthrower2 7y ago
  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.
  - eropple 7y ago
    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.
    - pgwhalen 7y ago
      How often are you sorting something where N is great enough for it to matter how the sorting works? I spend most of my time choosing data structures such that sorting anything other than handful of elements is unnecessary.
  - dkersten 7y ago
Animats 7y ago
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.
- gopalv 7y ago
  > 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#The_array_case https://en.wikipedia.org/wiki/Dutch_national_flag_problem#Th...
- lemagedurage 7y ago
  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.
  - loeg 7y ago
    GP is talking about radix sort, basically. If you know all your keys are integers you can sort in O(n log k) (k is maximal key width in bits).
slivanes 7y ago
For an audio representation of TimSort: https://www.youtube.com/watch?v=xoR-1KwQh2k&t=274s https://www.youtube.com/watch?v=xoR-1KwQh2k&t=274s
- war1025 7y ago
  I watched probably ten minutes of that video. Don't know that I learned anything, but it was sort interesting.
westurner 7y ago
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-and-complex-sorts https://docs.python.org/3/howto/sorting.html#sort-stability-... [2] https://docs.python.org/3/library/stdtypes.html#list.sort https://docs.python.org/3/library/stdtypes.html#list.sort [3] https://docs.python.org/3/library/functions.html#sorted https://docs.python.org/3/library/functions.html#sorted [4] https://en.wikipedia.org/wiki/Timsort https://en.wikipedia.org/wiki/Timsort
ken 7y ago
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.
- leshow 7y ago
  And Rust, the rust std lib uses a modified timsort/mergesort
  - cbarrick 7y ago
    FWIW, Rust uses Pattern-defeating quicksort for it's unstable sort. [1] https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort [2] https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_unstable https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor...
- rsfinn 7y ago
  Technically Swift uses a "modified" version of Timsort that "performs straight merges instead of adopting timsort's galloping strategy" [0]. [0] https://github.com/apple/swift/pull/19717 https://github.com/apple/swift/pull/19717
CJefferson 7y ago
I 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 https://github.com/orlp/pdqsort Basically, timsort is to mergesort as pdqsort is to quicksort.
social_quotient 7y ago
I always thought this sort visualizer was cool http://sorting.at/ http://sorting.at/
xiaodai 7y ago
radixsort is better still
- isatty 7y ago
  Only for numbers.
unnouinceput 7y ago
I, for one, cannot wait that quantum computing to be the norm, like current one is. Then the only algorithm everyone will use will be randomsort. Got a list to sort it? Allocate one q-bit for each element and apply randomsort and boom, done in under a picosecond, regardless of list size. This is the ultimate algorithm to be implemented for parallelization, all others will take more since they depend on sequence input.
- zitterbewegung 7y ago
  That’s not how it works . Grovers algorithm takes O(sqrt(n)) using a quantum computer . Values in a quantum computer are superpositions but when measured they will return only one result. They don’t have an infinite amount of time and or space .
  - unnouinceput 7y ago
    We are today on quantum computing where we were in 18th century when Ada was creating the 1st computer program. Sure, Grover's algorithm is good for current state of quantum computing but when it will reach to be a current norm just like the Silicon based one is today then is entire state altogether. By that time Grover's algorithm will take it's place in history but will not be used in practice. From wiki: Perform the following "Grover iteration" r(N) times. Iteration? That means one state of the computation is waiting for a previous one to be completed. That, to me, sounds like not a true parallelization algorithm, hence randomsort still wins.
    - saagarjha 7y ago
      I suggest you read up on how superposition works in quantum computers–they not just computers with an infinite number of cores :/
      - unnouinceput 7y ago
        No, they are not. Also 128 billion is a big enough number that if you'd say to a 18th century scientist who was working with punch cards computers that in the future one with 128 billion punch cards would exists he would've replied something along the lines, just like you, that there are not enough trees on Earth to create 128 billion cards for a single computer, let alone billion of them that they are more common than horses in 18th century. And yet, here we are, with computers that have 128 GB RAM, like the one I use to reply to you. So how about you let me dream big instead, eh?
person_of_color 7y ago
How to be THIS good as a Software Engineer?
- kragen 7y ago
  Practice, challenge yourself constantly, seek mentorship, humbly request feedback and act on it, and devote your life to the craft, not your wallet or your family. I think. Read Hamming.
  - purplezooey 7y ago
    Easier said than done
    - sanjayts 7y ago
      If it was easy, folks wouldn't have to ask how it could be done and everyone would that THAT good. ;)
  - chamoda 7y ago
    http://www.paulgraham.com/hamming.html http://www.paulgraham.com/hamming.html
longemen3000 7y ago
other sorting algorithm, taking advantage of SIMD instructions and being cache-aware, chipsort: https://github.com/nlw0/ChipSort.jl https://github.com/nlw0/ChipSort.jl
banachtarski 7y ago
Thanks for editing what was originally an inane title "Timsort the sort you haven't heard of" to describe something I (and probably most here) have heard of many times over and over again.
alexnewman 7y ago
That's why I encode all my data in a format optimized for galloping mode. Just kidding. That'd be sweet though
purplezooey 7y ago
It's an awesome idea, but seems to cross the line into "exploiting specific properties of the input", even if just a little, which would impact it's usefulness in say, a general purpose library.
justAlittleCom 7y ago
I dont understand how it is so special. Every single realworld sort I have seen are hybrid sorts. Very often merge sort + insertion sort or bubble sort for small sub-array. Can you englight me ?
CogitoCogito 7y ago
Here is a video I made a while back to better visualize the runs of timsort: https://www.youtube.com/watch?v=ZxLxf5xqqyE https://www.youtube.com/watch?v=ZxLxf5xqqyE Might be of interest...
sclangdon 7y ago
Isn't this the same idea as the Introsort[1], which was created in 1997 (four years earlier) and is the default sorting algorithm in C++'s standard library (and .NET framework since 4.5)? [1] https://en.wikipedia.org/wiki/Introsort https://en.wikipedia.org/wiki/Introsort

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

kbd 7y ago
Note that this is true for any (edit: stable, nlogn) merge sort.
- ThreeFx 7y ago
  Not true in general, however IIRC it is the case if you want optimal (i.e. n log n) time complexity.
  - beagle3 7y ago
    Not even in that case. Heapsort guarantees worst case n log n, and so does quicksort if you use an O(n) median selecting algorithm. Stable sorts often do require that, (mergesort is usually stabble, heapsort and quicksort are inherently not), but even that's not required - there is a completely in-place variant of merge sort that only requires O(log n) space for stack (like quicksort; heapsort is O(1)). See e.g. https://xinok.wordpress.com/2014/08/17/in-place-merge-sort-demystified-2/ https://xinok.wordpress.com/2014/08/17/in-place-merge-sort-d...
    - saagarjha 7y ago
      Apparently there is a O(n log n) time, O(1) space, stable sort: https://en.wikipedia.org/wiki/Block_sort https://en.wikipedia.org/wiki/Block_sort
- CraneWorm 7y ago
  you can do merge sort in place
  - hinkley 7y ago
    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 think claimed log n but was so complicated I never did figure out why it was supposed to work. At least one of these had higher time complexity, but often enough you need to work with data sets that dominate your memory footprint. Even a second array of pointers might push you over.
    - z0r 7y ago
      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.5514&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22....
      - hinkley 7y ago
        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.
        z0r 7y ago
        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)
- billforsternz 7y ago
  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.
  - srgpqt 7y ago
    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.
    - billforsternz 7y ago
      Thanks for the explanation, makes sense. I was tempted to classify this as "irrelevant to me", but then I remembered an application I had recently where I had values (chess games) that I was sorting which I didn't want to reorder if they were adjacent (as far as the sort was concerned) but not identical. Ended up adding an "original order" field as a sort tiebreaker. As it happens a stable sort would have saved me the pain.
  - cdirkx 7y ago
    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.
    - billforsternz 7y ago
      Thanks for the explanation, interesting.
  - hinkley 7y ago
    Said another way, if I sort my database by user names, the John Smith who has been my customer the longest always comes first in the line of John Smiths. One of the things you can do with a stable sort is to fake complex sorting by iteratively sorting by each criteria. Though I have rarely seen that be practical anywhere other than tabular data.
- kragen 7y ago
  Interestingly, the Golang standard library has a sort in it that claims to be a stable in-place O(N log N) mergesort.

Never heard of since it was last discussed on HN: https://news.ycombinator.com/item?id=17436591 https://news.ycombinator.com/item?id=17436591

dang 7y ago
And https://news.ycombinator.com/item?id=17883461 https://news.ycombinator.com/item?id=17883461 after that. Quite a few submissions for something no one has heard of: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=Timsort&sort=byDate&type=story https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... The other main discussions are 2011: https://news.ycombinator.com/item?id=3214527 https://news.ycombinator.com/item?id=3214527 2009: https://news.ycombinator.com/item?id=752677 https://news.ycombinator.com/item?id=752677

Beldin 7y ago

I heard of it from a talk about a bug in the implementation of TimSort in several popular libraries [1]. That bug should be fixed in Java, Android and Python. If you're using another language, you might want to verify that the bug is fixed/not present in your library [1] http://www.envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ http://www.envisage-project.eu/proving-android-java-and-pyth...

timothycrosley 7y ago

As an (unrelated to the Algorithm) Python developer, also named Tim, I've never been able to hear the last of it. Still a great algorithm, though!

pwinnski 7y ago

I think most Python devs have heard of this, as well as avid followers of HN, of course.

Congeec 7y ago

There are cases where pattern defeating sort beats timsort https://github.com/EmuraDaisuke/SortingAlgorithm.HayateShiki https://github.com/EmuraDaisuke/SortingAlgorithm.HayateShiki

purplezooey 7y ago
"external area" tho

pitaj 7y ago

Rust uses timsort as the stable sorting algorithm in its standard library. https://doc.rust-lang.org/std/primitive.slice.html#method.sort https://doc.rust-lang.org/std/primitive.slice.html#method.so...

tsegratis 7y ago

WikiSort should even be faster still Original author: https://github.com/BonzaiThePenguin/WikiSort https://github.com/BonzaiThePenguin/WikiSort Graph and copyage (by me): https://tse.gratis/aArray/#details https://tse.gratis/aArray/#details Or grail sort: https://github.com/Mrrl/GrailSort/blob/master/README.md https://github.com/Mrrl/GrailSort/blob/master/README.md Sort, is a deep rabbit hole

tsegratis 7y ago
WikiSort previous discussion https://news.ycombinator.com/item?id=7404223 https://news.ycombinator.com/item?id=7404223 Can't find a direct comparison with TimSort though..

james_s_tayler 7y ago

Heard about it by reading Java stacktraces one day.

fghorow 7y ago

Tim Peters is also the IEEE-754 guru for the Python codebase. Truly a giant of the Python community. <1/2 wink-ly yr's>

ignoramous 7y ago

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 code, post 1.5, is a joy to read, though verbose. Compilers and Languages seems to attract a certain caliber of engineers, I think. [1] https://bugs.openjdk.java.net/browse/JDK-6804124 https://bugs.openjdk.java.net/browse/JDK-6804124

stefan_ 7y ago
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_16 https://link.springer.com/chapter/10.1007/978-3-319-21690-4_...
- kevingadd 7y ago
  I found a similar problem using a fairly battle-tested C# implementation of timsort. Felt lucky that I had managed to reproduce it in a dev environment instead of it being a mysterious crash for users.
  - lqet 7y ago
    Many years ago, I copied an implementation of the Cohen-Sutherland algorithm (for line clipping) to C++ from pseudo code (I don't remember where I got this pseudo code from, but other sources used equivalent pseudo code). The code (it was a backend server code for a web app) was heavily tested with ab [0] and JMeter [1] against extreme load, everything seemed to worked fine. Fast-forward 6 months, when we had a sudden peak in users (for a few days, we went from around 500 visitors a day to around 500.000, which roughly meant > 5 million requests per day). Suddenly, the backend, which ran without problems for half a year, crashed in production every 5 hours or so with a segmentation fault. I could not for the life of me reproduce this. After some panicking, I let the backend run in gdb in production against the ~50 requests per second we were still getting. After a few hours, the segfault occurred again, and I figured out that on extremely rare edge cases, the pseudo code I copied to C++ divided by 0, which lead to chain of problems afterwards, eventually resulting in said segfault. If I remember correctly, the fix was trivial. [0] https://httpd.apache.org/docs/2.4/programs/ab.html https://httpd.apache.org/docs/2.4/programs/ab.html [1] https://jmeter.apache.org/ https://jmeter.apache.org/

mharrison 7y ago

Tim the enchanter!

boltzmannbrain 7y ago

"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-and-complex-sorts https://docs.python.org/2/howto/sorting.html#sort-stability-... https://stackoverflow.com/questions/10948920/what-algorithm-does-pythons-sorted-use https://stackoverflow.com/questions/10948920/what-algorithm-...

shiblukhan 7y ago
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.
quickthrower2 7y ago
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.
- eropple 7y ago
  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.
  - pgwhalen 7y ago
    How often are you sorting something where N is great enough for it to matter how the sorting works? I spend most of my time choosing data structures such that sorting anything other than handful of elements is unnecessary.
- dkersten 7y ago

Animats 7y ago

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.

gopalv 7y ago
> 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#The_array_case https://en.wikipedia.org/wiki/Dutch_national_flag_problem#Th...
lemagedurage 7y ago
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.
- loeg 7y ago
  GP is talking about radix sort, basically. If you know all your keys are integers you can sort in O(n log k) (k is maximal key width in bits).

slivanes 7y ago

For an audio representation of TimSort: https://www.youtube.com/watch?v=xoR-1KwQh2k&t=274s https://www.youtube.com/watch?v=xoR-1KwQh2k&t=274s

war1025 7y ago
I watched probably ten minutes of that video. Don't know that I learned anything, but it was sort interesting.

westurner 7y ago

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-and-complex-sorts https://docs.python.org/3/howto/sorting.html#sort-stability-... [2] https://docs.python.org/3/library/stdtypes.html#list.sort https://docs.python.org/3/library/stdtypes.html#list.sort [3] https://docs.python.org/3/library/functions.html#sorted https://docs.python.org/3/library/functions.html#sorted [4] https://en.wikipedia.org/wiki/Timsort https://en.wikipedia.org/wiki/Timsort

ken 7y ago

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.

leshow 7y ago
And Rust, the rust std lib uses a modified timsort/mergesort
- cbarrick 7y ago
  FWIW, Rust uses Pattern-defeating quicksort for it's unstable sort. [1] https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort [2] https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_unstable https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor...
rsfinn 7y ago
Technically Swift uses a "modified" version of Timsort that "performs straight merges instead of adopting timsort's galloping strategy" [0]. [0] https://github.com/apple/swift/pull/19717 https://github.com/apple/swift/pull/19717

CJefferson 7y ago

I 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 https://github.com/orlp/pdqsort Basically, timsort is to mergesort as pdqsort is to quicksort.

social_quotient 7y ago

I always thought this sort visualizer was cool http://sorting.at/ http://sorting.at/

xiaodai 7y ago

radixsort is better still

isatty 7y ago
Only for numbers.

unnouinceput 7y ago

I, for one, cannot wait that quantum computing to be the norm, like current one is. Then the only algorithm everyone will use will be randomsort. Got a list to sort it? Allocate one q-bit for each element and apply randomsort and boom, done in under a picosecond, regardless of list size. This is the ultimate algorithm to be implemented for parallelization, all others will take more since they depend on sequence input.

zitterbewegung 7y ago
That’s not how it works . Grovers algorithm takes O(sqrt(n)) using a quantum computer . Values in a quantum computer are superpositions but when measured they will return only one result. They don’t have an infinite amount of time and or space .
- unnouinceput 7y ago
  We are today on quantum computing where we were in 18th century when Ada was creating the 1st computer program. Sure, Grover's algorithm is good for current state of quantum computing but when it will reach to be a current norm just like the Silicon based one is today then is entire state altogether. By that time Grover's algorithm will take it's place in history but will not be used in practice. From wiki: Perform the following "Grover iteration" r(N) times. Iteration? That means one state of the computation is waiting for a previous one to be completed. That, to me, sounds like not a true parallelization algorithm, hence randomsort still wins.
  - saagarjha 7y ago
    I suggest you read up on how superposition works in quantum computers–they not just computers with an infinite number of cores :/
    - unnouinceput 7y ago
      No, they are not. Also 128 billion is a big enough number that if you'd say to a 18th century scientist who was working with punch cards computers that in the future one with 128 billion punch cards would exists he would've replied something along the lines, just like you, that there are not enough trees on Earth to create 128 billion cards for a single computer, let alone billion of them that they are more common than horses in 18th century. And yet, here we are, with computers that have 128 GB RAM, like the one I use to reply to you. So how about you let me dream big instead, eh?

person_of_color 7y ago

How to be THIS good as a Software Engineer?

kragen 7y ago
Practice, challenge yourself constantly, seek mentorship, humbly request feedback and act on it, and devote your life to the craft, not your wallet or your family. I think. Read Hamming.
- purplezooey 7y ago
  Easier said than done
  - sanjayts 7y ago
    If it was easy, folks wouldn't have to ask how it could be done and everyone would that THAT good. ;)
- chamoda 7y ago
  http://www.paulgraham.com/hamming.html http://www.paulgraham.com/hamming.html

longemen3000 7y ago

other sorting algorithm, taking advantage of SIMD instructions and being cache-aware, chipsort: https://github.com/nlw0/ChipSort.jl https://github.com/nlw0/ChipSort.jl

banachtarski 7y ago

Thanks for editing what was originally an inane title "Timsort the sort you haven't heard of" to describe something I (and probably most here) have heard of many times over and over again.

alexnewman 7y ago

That's why I encode all my data in a format optimized for galloping mode. Just kidding. That'd be sweet though

purplezooey 7y ago

It's an awesome idea, but seems to cross the line into "exploiting specific properties of the input", even if just a little, which would impact it's usefulness in say, a general purpose library.

justAlittleCom 7y ago

I dont understand how it is so special. Every single realworld sort I have seen are hybrid sorts. Very often merge sort + insertion sort or bubble sort for small sub-array. Can you englight me ?

CogitoCogito 7y ago

Here is a video I made a while back to better visualize the runs of timsort: https://www.youtube.com/watch?v=ZxLxf5xqqyE https://www.youtube.com/watch?v=ZxLxf5xqqyE Might be of interest...

sclangdon 7y ago

Isn't this the same idea as the Introsort[1], which was created in 1997 (four years earlier) and is the default sorting algorithm in C++'s standard library (and .NET framework since 4.5)? [1] https://en.wikipedia.org/wiki/Introsort https://en.wikipedia.org/wiki/Introsort