It was not apparent from your article how Timsort ensures stability. After doing some reading on my own I was able to discover that it is done so by only reversing strictly decreasing runs, and by never reordering runs.

While your description covers both of those points[1], it didn't mention them together as contributing to stability.

1: Actually rereading to make sure I didn't miss anything, you have a mistake, as you say: "Runs have to be strictly increasing or decreasing" while they have to be either monotonically increasing (i.e. non-decreasing) or strictly decreasing.

so: 1,2,2,3 is a run, but 3,2,2,1 is not.

The exposition of the sorting algorithm is beautiful and clear. Thanks!

Your disparaging of academic work is utterly ridiculous. I am a mathematician working in academia with real world data, developing algorithms that are used in industry. This sentence at the begining of your article makes me think that you are not really aware of how the real world works.

Sure. Why are you highlighting this wasn't "created in an academic laboratory". Do you think your blogging approach of thinly veiled negativity toward established peer-reviewed works will give you more likeability among the general readership?

Is the implementation at the end of the article complete? I don't see anything that looks like the "galloping" behavior described just prior.

Ooh, it's actually not complete. I put that as a placement while I tried to find the original source code for it. I didn't expect it to be shared anywhere. me. Thank you for bring this to my attention, I'll see if I can find the source code again, terribly sorry for doing the worst thing imaginable and publishing something that isn't complete!

> Since the algorithm has been invented it has been used as the default sorting algorithm in Python, Java, the Android Platform, and in versions of GNU.

I'm glad you mentioned how far the algorithm has spread to other languages since originating in Python. But, "versions of GNU" what?

I assume he means sort/gsort, from the coreutils.

http://git.savannah.gnu.org/cgit/coreutils.git/tree/src/sort... says:

   Use a recursive divide-and-conquer algorithm, in the style
   suggested by Knuth volume 3 (2nd edition), exercise 5.2.4-23.  Use
   the optimization suggested by exercise 5.2.4-10; this requires room
   for only 1.5*N lines, rather than the usual 2*N lines.  Knuth
   writes that this memory optimization was originally published by
   D. A. Bell, Comp J. 1 (1958), 75.

Versions of GNU. Although it's rare to see this term being used in this context these days, "GNU" was invented as a name of an operating system.

Where is TimSort used in a GNU operating system?

I suspect this line originates from the Wikipedia entry for TimSort with the line:

"Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7,[3] on the Android platform,[4] and in GNU Octave."

Notice how the order of Python, Java, Android, and GNU is the same? My tentative hypothesis is that "Octave" was dropped, and that "GNU" here means something more like "in the GNU project."

Also, the author uses a time complexity table with Ω(), Θ(), and O() notations, but suggests "To learn about Big O notation", go to another hackernoon article which only talks about O() and not big omega or big theta notations.

That raises the question, what does the Hurd kernel use timsort for?

In your example of reversing decreasing runs, you dropped a 9.

Thank you so much!

another minor typo:

> do the merging as soon as possible to exploit the run that the run just found is still high in the memory hierarchy

s/run/fact/ if I'm reading correctly

for the python timsort, the original source code is here: https://svn.python.org/projects/python/trunk/Objects/listobj..., although porting it to idiomatic python definitely seems nontrivial

Also, it looks like the pypy implementation is here: https://bitbucket.org/pypy/pypy/src/default/rpython/rlib/lis...

Python is using Git these days:

https://github.com/python/cpython/blob/master/Objects/listob...

Oops, thanks! That's much better. Not sure why I stumbled on the svn link first.