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