3 ms·
Since you sort by digit, if you're going to make your radix be the size of an integer, you'll to construct that many empty lists; in actual practical implementa
by jacobolus 16y ago
Since you sort by digit, if you're going to make your radix be the size of an integer, you'll to construct that many empty lists; in actual practical implementations of radix sort, the radix is some relatively small number, and so you end up with O(nk). I guess if you want you can say that k is actually O(log(maxint)), if all of your integers are < maxint. But that ends up being quite a sizable constant term if you really want to consider it constant. If you're going to do algorithmic analysis that entirely ignores large constants, it's a bit strange to simultaneously declare that all your integers will be bounded by some particular cutoff.