It's an awesome idea, but seems to cross the line into "exploiting specific properties of the input", even if just a little, which would impact it's usefulness in say, a general purpose library.
Timsort, the Python sorting algorithm
91–100 of 135 posts
Re: Timsort, the Python sorting algorithm
#92There are cases where pattern defeating sort beats timsort https://github.com/EmuraDaisuke/SortingAlgorithm.HayateShiki
"external area" tho
Re: Timsort, the Python sorting algorithm
#93Re: Timsort, the Python sorting algorithm
#94My favourite TimSort story is of ex-Sun employee, Joshua Bloch of Effective Java fame. J Bloch was in audience at the time when Tim Peters presented his new algorithm to sort a list, and he was so blown away that he started porting Tim's implementation right there with an intent to commit it to the JDK mainline [0], which he eventually did [1]. [0] Some of the core JDK developers are really on another level. The JDK…
TimSort—more specifically, Bloch's 9 line "rangecheck" function from his reimplementation—figured into Oracle's claims that Google copied Java code into Android:
http://www.groklaw.net/articlebasic.php?story=20120419221941...
As best as I can remember, those 9 lines are the only literal copying Oracle was able to find; the rest of their suit centers around whether the design of an API (e.g. parameter names) can be copyrighted. (And unless the Supreme Court steps in, the answer is "maybe.")
Re: Timsort, the Python sorting algorithm
#95Earlier quoted context omitted.
That’s not how it works . Grovers algorithm takes O(sqrt(n)) using a quantum computer . Values in a quantum computer are superpositions but when measured they will return only one result. They don’t have an infinite amount of time and or space .
We are today on quantum computing where we were in 18th century when Ada was creating the 1st computer program. Sure, Grover's algorithm is good for current state of quantum computing but when it will reach to be a current norm just like the Silicon based one is today then is entire state altogether. By that time Grover's algorithm will take it's place in history but will not be used in practice. From wiki: Perform t…
I suggest you read up on how superposition works in quantum computers–they not just computers with an infinite number of cores :/
Re: Timsort, the Python sorting algorithm
#96You can beat O(n log n). That limit is for sorts that use only a ">" comparison. A distribution sort, where you distribute the keys over buckets, can approach O(n). The first software patent, for SyncSort, is for a sort that beats O(n log n). The basic idea is to read records for a while, get some stats about the key distribution, and set up the buckets to get a roughly equal fraction of the observed keyspace. If blo…
Shameless plug: A couple years ago I wrote an article about where this O(n log n) bound comes from if anyone is interested: "Comparison Sorting Algorithms and Mystery of NlogN complexity" https://medium.com/@kamyarg/comparison-sorting-algorithms-an...
It's not some obscure fact. At least it was taught in my bachelor intro to algorithms class, along with the Stirling formula as part of the proof.
Re: Timsort, the Python sorting algorithm
#97Earlier quoted context omitted.
Great, yet another True-Scotsman of being a proper developer. There is so much you should have read, googled, written to be a "True" dev these days. My theory is - if you are often learning stuff and producing good working code be happy. Not every developer needs to know the underlying sort algorithms.
His point is a great many people are familiar with this algorithm by way of working with Python. You can certainly be happy not knowing the tools of your trade very intimately, but that's definitely not something to encourage.
I took the tone to be more incredulous with the "??" and "I would hope".
Re: Timsort, the Python sorting algorithm
#98Besides Python and Java, it's also the sorting algorithm used by Chrome, Android, and Swift. At this point I think more than half the world's programmers are using Timsort, whether they realize it or not.
Technically Swift uses a "modified" version of Timsort that "performs straight merges instead of adopting timsort's galloping strategy" [0].
Re: Timsort, the Python sorting algorithm
#99Earlier quoted context omitted.
Python sort works on generic objects that probide ">=", not more specific types. For the generic algorithm, as I'm sure you're aware, O(n log n) is optimal. And yes, radix sorts are something like O(n log k), where k is the bitwidth of the maximal key. Since k is often a constant this could be thought of as O(n). A Python sort could enumerate the list, check for all (1) integer contents and (2) no overridden comparat…
nit: runtime for radix sort is O(nk), since you sort the full list by each of the digits, sequentially. I've always thought claiming radix sort on integers to be linear was a bit disingenuous, since k In fact, if your integers are all unique, then k >= log(n). (for consistent choice of base for log)
> (for consistent choice of base for log)
It's not clear the choice of log should be consistent. For radix sort the number of iterations is the log of the max element in the base of the number of buckets. For a merge sort the number of comparisons is pretty close to log-base-two of the number of elements to sort. (Not exactly -- to merge n items you need n-1 comparisons, not n.)
Of course, asymptotically they're the same -- lg(n) == log(n) etc -- and we're counting comparisons on one two-fingered hand and divs+mods on the other, so non-asymptotic comparisons don't make much sense without also talking about benchmarks.
Re: Timsort, the Python sorting algorithm
#100Earlier quoted context omitted.
Radix sort is worst case O(n). (which is what I'm assuming the parent commenter is referring to) It's not n in common situations, but nlogn in pathological cases the way Timsort is. The reason is it "violates" the n logn lower bound of comparison sorts is because it isn't a comparison sort. Sort of like how hash table lookups "violate" the O(log n) average lower bound of binary tree lookups. It has different performa…
No, radix sort is worst case O(n * k). In many common cases, k ~= log(n). IN certain specific cases, k < log(n), and specifically for cases where you have a very large n, but a bounded number of values (say, you're sorting 10 billion 4-bit ints), k can be considered a constant. But that is by no means generally true.
In most cases k << n. For 64-bit integers, byte wise radix sort k is 8, which is less than log n whenever n is more than 256. So, radix sort is typically much faster than an O(n log n) sort of your data support it. It just isn’t as widely used because it is not as general as a comparison based sort.