4 ms·
You 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
by Animats 7y ago
You 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 blocks of records show up with very different stats, action has to be taken to adjust the bucketing.
- gopalv 7y ago> 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 Hadoop Terasort does the same thing of sort, which is to start off with a partitioner doing a radix sort & then sort each part with a lower O number of comparisons (the Spark one actually does local sorts and then has the merge-sort part just fetch ranges after first pass), however those two work great when the key ranges are almost entirely unique with no big runs of identical keys and differing values. The Timsort one however has an advantage when there are huge runs of identical values or almost sorted inputs, like when you have a time-series with the occasional out of order packet. The galloping mode in the algorithm neatly eats those ranges up very fast. My favourite example to show sorting is data dependent is the tricolor sort example[1], which illustrates what happens when you have a large number of identical keys. [1] - https://en.wikipedia.org/wiki/Dutch_national_flag_problem#The_array_case https://en.wikipedia.org/wiki/Dutch_national_flag_problem#Th...
- lemagedurage 7y agoBig O notation is about the theoretical upper bound of an algorithm. Clever data-based tricks like putting items in buckets or gathering statistics are unrelated to this notation as they rely on a certain consistency. Maybe you should call it average run time on typical data.
- loeg 7y agoGP is talking about radix sort, basically. If you know all your keys are integers you can sort in O(n log k) (k is maximal key width in bits).
- joshuamorton 7y agoYou have a bit of a repetition here backwards. You can sort in O(n * k), where k is the maximal key width in bits. This ends up being O(n log(k)). Your formulation suggests radix sort running in O(n log(log(k))), which isn't quite true.
- loeg 7y agoSorry, my mistake -- you're totally right. Number of bits is log_2(k), where k is just the maximal key number.
- nwallin 7y agoRadix 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 performance bounds because it's a different problem.
- joshuamorton 7y agoNo, 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.
- bloomer 7y agoIn 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.
- joshuamorton 7y agoAfter a byte-wise radix sort you still have to sort within each bucket. In the worst case, every element falls into a single bucket, at which point your best best is to do a bit wise radix sort over the low 8 bits. This ends up being equivalent to k=log(n).
- gigatexal 7y agoJumping in this fascinating thread about sorting to ask what the double less than chevrons mean? I know what one means but what do two of them mean?
- 7y ago
- loeg 7y agoPython 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 comparator method, and then use a radix sort, I guess.
- vitus 7y agonit: 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 << log(n) only if your list has a lot of duplicate entries. In fact, if your integers are all unique, then k >= log(n). (for consistent choice of base for log)
- loeg 7y agoYou're totally right. joshuamorton made the same correction on another comment where I made the same error. Mea culpa!
- repsilat 7y ago> (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.
- kamyarg 7y agoShameless 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-and-mystery-of-nlogn-complexity-d7e80c34876 https://medium.com/@kamyarg/comparison-sorting-algorithms-an...
- bonoboTP 7y agoIt'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.
- thehappypm 7y agoCounting sorts are super neat and O(n), if the number of unique items is really small. Imagine a list of all 0s and 1s that you wanted to sort (like 001110101). Why bother sorting? Just count up how many 0’s and 1’s there are (four 0’s, five 1’s) and generate the sorted list. O(n). Clearly this doesn’t work when you have real world data to sort, but it is the basis for a radix sort, where you sort a batch of numbers digit-by-digit, giving you O(n*d). Though I think it’s rarely used.
- jeffasinger 7y agoWe did actually get to use it at work, to real performance benefit. We have a leaderboard with a list of users, which is normally a list of users totalling between 2 to 50,0000, but in rare circumstances can be several million. The scores users can achieve are in a rather small range, perhaps only 450k valid different scores, and we were doing this sort on average once every 30 seconds. What we ended up doing was switching to a radix sort when the list of users got to be very long, as it was substantially faster in those cases, making the user experience much better, as the leaderboard was much more up to date for the very large cases.