4 ms·

Hey! Author here! Thank you so much for posting this here! If you have any questions feel free to ask me

by bbno4 8y ago

kbd 8y ago
> 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?
- deleted 8y ago
  [deleted]
- LeoPanthera 8y ago
  I assume he means sort/gsort, from the coreutils.
  - eesmith 8y ago
    http://git.savannah.gnu.org/cgit/coreutils.git/tree/src/sort.c#n3175 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.
- seba_dos1 8y ago
  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.
  - copperx 8y ago
    That raises the question, what does the Hurd kernel use timsort for?
  - eesmith 8y ago
    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.
Anm 8y ago
In your example of reversing decreasing runs, you dropped a 9.
- bbno4 8y ago
  Thank you so much!
  - czr 8y ago
    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/listobject.c https://svn.python.org/projects/python/trunk/Objects/listobj..., although porting it to idiomatic python definitely seems nontrivial
    - jwilk 8y ago
      Python is using Git these days: https://github.com/python/cpython/blob/master/Objects/listobject.c https://github.com/python/cpython/blob/master/Objects/listob...
      - czr 8y ago
        Oops, thanks! That's much better. Not sure why I stumbled on the svn link first.
    - czr 8y ago
      Also, it looks like the pypy implementation is here: https://bitbucket.org/pypy/pypy/src/default/rpython/rlib/listsort.py?fileviewer=file-view-default https://bitbucket.org/pypy/pypy/src/default/rpython/rlib/lis...
alexbecker 8y ago
Is the implementation at the end of the article complete? I don't see anything that looks like the "galloping" behavior described just prior.
- bbno4 8y ago
  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!
aidenn0 8y ago
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.
quickben 8y ago
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?
enriquto 8y ago
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.

Hey! Author here! Thank you so much for posting this here! If you have any questions feel free to ask me

by bbno4 8y ago

Hey! Author here! Thank you so much for posting this here! If you have any questions feel free to ask me

kbd 8y ago

> 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?

deleted 8y ago
[deleted]
LeoPanthera 8y ago
I assume he means sort/gsort, from the coreutils.
- eesmith 8y ago
  http://git.savannah.gnu.org/cgit/coreutils.git/tree/src/sort.c#n3175 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.
seba_dos1 8y ago
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.
- copperx 8y ago
  That raises the question, what does the Hurd kernel use timsort for?
- eesmith 8y ago
  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.

Anm 8y ago

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

bbno4 8y ago
Thank you so much!
- czr 8y ago
  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/listobject.c https://svn.python.org/projects/python/trunk/Objects/listobj..., although porting it to idiomatic python definitely seems nontrivial
  - jwilk 8y ago
    Python is using Git these days: https://github.com/python/cpython/blob/master/Objects/listobject.c https://github.com/python/cpython/blob/master/Objects/listob...
    - czr 8y ago
      Oops, thanks! That's much better. Not sure why I stumbled on the svn link first.
  - czr 8y ago
    Also, it looks like the pypy implementation is here: https://bitbucket.org/pypy/pypy/src/default/rpython/rlib/listsort.py?fileviewer=file-view-default https://bitbucket.org/pypy/pypy/src/default/rpython/rlib/lis...

alexbecker 8y ago

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

bbno4 8y ago
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!

aidenn0 8y ago

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.

quickben 8y ago

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?

enriquto 8y ago

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.