Hacker News Reader

Comment by Animats | Hacker News Reader

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.

View on HN

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.

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 comparator method, and then use a radix sort, I guess.

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

You're totally right. joshuamorton made the same correction on another comment where I made the same error. Mea culpa!

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

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

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

> 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#Th...

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

GP 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).

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

Sorry, my mistake -- you're totally right. Number of bits is log_2(k), where k is just the maximal key number.

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 performance bounds because it's a different problem.

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.

After 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).

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

https://www.google.com/search?q=what+does+<<+mean

Basically “much less than”.

In this context, it means "much less." It's used that way sometimes in mathematical discussions.

That logic isn't right. You can implement an O(n log n) sort with whatever log base/radix you want. It could be 2, it could be 256, it could be 4096. If you use the same base/radix for both n and k, then log n is close to k and probably smaller.

Which version ends up faster is mostly based on factors that big O notation doesn't capture easily. You have to push things to impractical numbers like n=2^1000 or 2^1000000 to properly distinguish between constant factors and log factors, and at that point it doesn't actually help you write better code.

The n log n bound is for comparison sorts, which Radix Sort is not an instance of.

Reply on news.ycombinator.com