Re:Timsort is a sorting algorithm that is efficient for real...
by LeoPanthera on Sunday July 01, 2018 @04:48PM
(#17437473)
I assume he means sort/gsort, from the coreutils.
Re:Timsort is a sorting algorithm that is efficient for real...
by eesmith on Sunday July 01, 2018 @05:36PM
(#17437758)
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.
Re:Timsort is a sorting algorithm that is efficient for real...
by seba_dos1 on Sunday July 01, 2018 @04:53PM
(#17437503)
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.
Re:Timsort is a sorting algorithm that is efficient for real...
by eesmith on Sunday July 01, 2018 @05:54PM
(#17437842)
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.
I'm glad you mentioned how far the algorithm has spread to other languages since originating in Python. But, "versions of GNU" what?