4 ms·

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

by 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.

by kbd 8y ago

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.