Radix sort - Wikipedia, the free encyclopedia: "Radix sort's efficiency is O(k·n) for n keys which have k or fewer digits. Sometimes k is presented as a constant, which would make radix sort better (for sufficiently large n) than the best comparison-based sorting algorithms, which are all O(n·log(n)). However, in general k cannot be considered a constant. In particular, under the common (but sometimes implicit) assumption that all keys are distinct, then k must be at least of the order of log(n), however other sorting methods become O(log (n) * log (n) * n) under similar constraints as they also need to step through an ever increasing number of symbols to do the comparisons."
