He's essentially cheating. When he analyzes the algorithm presented, he says "I’ll now describe an algorithm that does not depend on the word length. For any word length w, w ≥ log n, it sorts n word-sized integers in time proportional to n log log n."
But that's entirely cheating. If you give the same assumption to radix sort, then you could say "For any word length w, w ≥ log n, radix sort sorts n word-sized integers in time proportional to n". Which is much better.
The only time radix sort actually goes slower than linear time is when the size of the integers is not polynomial in n. If the size of the integers is exponential n, I think this algorithm would similarly slow down, as it would take a linear number of words to represent a single integer, meaning that it would take log n reductions to get the integers to fit into a single word, not log log n as he assumes.
Comments
He's essentially cheating. When he analyzes the algorithm presented, he says "I’ll now describe an algorithm that does not depend on the word length. For any word length w, w ≥ log n, it sorts n word-sized integers in time proportional to n log log n."
But that's entirely cheating. If you give the same assumption to radix sort, then you could say "For any word length w, w ≥ log n, radix sort sorts n word-sized integers in time proportional to n". Which is much better.
The only time radix sort actually goes slower than linear time is when the size of the integers is not polynomial in n. If the size of the integers is exponential n, I think this algorithm would similarly slow down, as it would take a linear number of words to represent a single integer, meaning that it would take log n reductions to get the integers to fit into a single word, not log log n as he assumes.