3 ms·

No general purpose sorting algorithm period can do better than O(n * log(n)), regardless of comparison or otherwise. For a radix sort with a complexity of O(n *

by Kranar 5y ago

No general purpose sorting algorithm period can do better than O(n * log(n)), regardless of comparison or otherwise. For a radix sort with a complexity of O(n * w) where w is the key length, w converges to log(n) in the general case since the number of bits needed to represent n values grows logarithmically with n, hence you arrive back to O(n * log(n)). The O(n * log(n)) is an information theoretic result that applies even to radix sort, to be more precise the optimal sorting algorithm is Θ(n!). If you fix w to a constant, then certainly one can claim that radix sort is O(n), but then so are comparison sorts as well. That's not to say that radix sort isn't useful in practice, just because two sorting algorithms have the same asymptotic bounds doesn't mean they are equal, but it is to say that its performance is a matter of evaluating the constants rather than how it scales.

cyber_kinetist 5y ago
Maybe it has more to do with the actual distribution/form of the data? From my understanding radix sort can be incredibly fast when the numbers have fixed digits and evenly distributed in a predefined range (like phone numbers) but will be ineffective for floating point numbers or uneven distributions with extreme outliers.
cb321 5y ago
> since the number of bits needed to represent n values grows logarithmically with n What you say only applies to sorting n unique/distinct keys. With no prohibition on duplicate keys, n & w vary quite independently. In this more general setting, radix sorting is indeed "really" O(nw) and w could be like 8 bits for some giant data set (EDIT and order is absolutely a useful property even with dups since there can be satellite data with the keys - also possibly bounded!). This is a common talking past each other problem in this area. To your credit you made this assumption explicit. (EDIT: "General purpose" may have some semantic unclarity, I suppose.) In terms of relevance, everyone has their own, but my personal experience is that most (but not all) real world data allow both duplicate keys and bounding key width. In particular, the largest n data sets have been the least likely to have a prohibition on duplicate keys, and also the most likely to have small w (with a few exceptions). The random access pattern of memory writes in the passes of a radix sort may (or may not) be a problem, and constant factors matter, of course (as you also say). So tying w to n was has always seems a very special and somewhat artificial case to me. I also have never heard of any practical O(n) comparison sort for fixed w before. Can you perhaps give a reference to some such algorithm? Thanks!
- jameshart 5y ago
  At some level, even comparing ‘a<b’ has a complexity related to the log of the magnitude of a and b. So if you’re doing a comparison sort over n unique values surely you’re going to run into a similar log n factor that the gp threw at the radix sort?
  - cb321 5y ago
    It depends how you count. There can be O(n log(n)^2) as you say, but I believe there are some comparison based algos where you only have to compare "fewer bits" to decide each comparison. So bit-wise cmps might still be O(n log n). However, you do have to move whole w-bit keys which is w bits wide. So, in full cost (cmp + space moves) unless you can do tricks to avoid the whole move, the comparison sorts do scale worse than radix-like digital sorts. And on general purpose CPUs people certainly compare batches of 8/16/32/64 bits at a time in HW. Personally, I think radix really does scale better, but maybe @Kranar can clarify his claim. (EDIT: there is often a random write pattern to digital sorts that can slow them down at massive scales, but that is definitely an {important} constant factor/different kind of "real machine" analysis.)

by Kranar 5y ago

cyber_kinetist 5y ago

Maybe it has more to do with the actual distribution/form of the data? From my understanding radix sort can be incredibly fast when the numbers have fixed digits and evenly distributed in a predefined range (like phone numbers) but will be ineffective for floating point numbers or uneven distributions with extreme outliers.

cb321 5y ago

> since the number of bits needed to represent n values grows logarithmically with n What you say only applies to sorting n unique/distinct keys. With no prohibition on duplicate keys, n & w vary quite independently. In this more general setting, radix sorting is indeed "really" O(nw) and w could be like 8 bits for some giant data set (EDIT and order is absolutely a useful property even with dups since there can be satellite data with the keys - also possibly bounded!). This is a common talking past each other problem in this area. To your credit you made this assumption explicit. (EDIT: "General purpose" may have some semantic unclarity, I suppose.) In terms of relevance, everyone has their own, but my personal experience is that most (but not all) real world data allow both duplicate keys and bounding key width. In particular, the largest n data sets have been the least likely to have a prohibition on duplicate keys, and also the most likely to have small w (with a few exceptions). The random access pattern of memory writes in the passes of a radix sort may (or may not) be a problem, and constant factors matter, of course (as you also say). So tying w to n was has always seems a very special and somewhat artificial case to me. I also have never heard of any practical O(n) comparison sort for fixed w before. Can you perhaps give a reference to some such algorithm? Thanks!

jameshart 5y ago
At some level, even comparing ‘a<b’ has a complexity related to the log of the magnitude of a and b. So if you’re doing a comparison sort over n unique values surely you’re going to run into a similar log n factor that the gp threw at the radix sort?
- cb321 5y ago
  It depends how you count. There can be O(n log(n)^2) as you say, but I believe there are some comparison based algos where you only have to compare "fewer bits" to decide each comparison. So bit-wise cmps might still be O(n log n). However, you do have to move whole w-bit keys which is w bits wide. So, in full cost (cmp + space moves) unless you can do tricks to avoid the whole move, the comparison sorts do scale worse than radix-like digital sorts. And on general purpose CPUs people certainly compare batches of 8/16/32/64 bits at a time in HW. Personally, I think radix really does scale better, but maybe @Kranar can clarify his claim. (EDIT: there is often a random write pattern to digital sorts that can slow them down at massive scales, but that is definitely an {important} constant factor/different kind of "real machine" analysis.)