# A question about sorting

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

## 1 Answer

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
@GerryMyerson Yes. Edited it. Thanks. – user17762 May 24 '12 at 1:24
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
The nlogn lower bound is applicable only to comparison based sorts. There are other sorts with almost linear time complexity (of course they have other bizarre shortcomings making them impractical) For example, Counting Sort – TenaliRaman May 24 '12 at 3:24