Hey! Author here! Thank you so much for posting this here! If you have any questions feel free to ask me
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.
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.
I'm glad you mentioned how far the algorithm has spread to other languages since originating in Python. But, "versions of GNU" what?
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.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.
> 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
https://github.com/python/cpython/blob/master/Objects/listob...