I've always been thought that the fastest way to sort an array of numbers has complexity $O(n \log (n))$. However, radix sort has complexity $O(kn)$ where $k$ is the number of bits. There are even questions on the internet where it is asked to prove that a sorting algorithm cannot be faster than $n \log (n)$.

Wanted to have a clarification on this. Does radix sort have any limitations? If not, is the lower bound on sorting linear in the number of elements?

-
Maybe I misunderstand, but isn't the number of bits needed to store $n$ about $\log n$? –  froggie May 24 '12 at 1:13
nlog(n) is the bound on comparison sorts, where the only thing you are given is a relation R(x,y) which compares x and y. If you have additional information about elements (which is the case with radix sort) you can sort faster. –  Mark May 24 '12 at 1:16
I'm not sure if this helps but there are (randomised) algorithms that are certainly faster than $\mathcal{O}(nlog(n))$. For example: M. Thorup. Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations. Journal of Algorithms, Volume 42, Number 2, February 2002, pp. 205-230(26) [reference from wikipedia]. Also I remember in one of our classes the professor was talking about "bucket sort" which has O(n) as "expected" time! –  Keivan May 24 '12 at 1:18
@froggie: If you're counting such things, don't forget that a comparison would also takes $O(\log n)$ time rather than $O(1)$ time in the worst case! –  Hurkyl May 24 '12 at 1:35
@froggie Almost, take the example of $256_{(10)}$, the number of bits required for it is $9$, contrary to the output of $log_2(256) = 8$. That's because in an $n$-bit binary value, the highest power is $2^{n-1}$ which would be, in the case of 8 bits, $128$. The highest value expressible, therefore, is $2^n - 1$ (for all bits to be $1$, evaluating to $255$). Therefore, the actual number of bits required for $n$ is $log_2(n)+1$ (trunc the fractional part). Therefore, you actually can only express $n$ with that many bits, even though a lot more falls into that range ($n_{max}=2^{log_2(n)+1}-1$). –  Domagoj Pandža May 24 '12 at 1:51

The number of bits $k$ cannot be considered constant in general. In fact, if all the $n$ numbers are distinct then $k = \mathcal{\Omega}(\log n)$. Hence, there is no difference between radix sort and other fast sorting algorithms.
More generally, any generic deterministic sorting algorithm cannot better $\mathcal{O}(n \log n)$ complexity. If you have $n$ numbers, then the number of comparisons you need to make is at least $\log_2(n!)$.
Shouldn't that last term be $\log_2(n!)$? –  Gerry Myerson May 24 '12 at 1:23
If all the $n$ numbers are distinct, isn't $k = \Omega(\log n)$ rather than $O(\log n)$? –  Rahul May 24 '12 at 1:26
@RahulNarain Yes. it should be $\Omega(\log n)$ and not $\mathcal{O}(\log n)$. –  user17762 May 24 '12 at 1:27