3 ms·
> it will happily beat other "faster" algorithms When it applies, there are essentially no faster algorithms - it’s O(n) if the word size is constant (it often
by beagle3 6y ago
> it will happily beat other "faster" algorithms
When it applies, there are essentially no faster algorithms - it’s O(n) if the word size is constant (it often is), which cannot be beat asymptotically. kr sort is only asymptotically better if word size is considered variable.
It’s irrelevant if you have no radix to sort on - comparison sort is provably at least O(n log n) which is slower.