Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
Maybe I misunderstand, but isn't the number of bits needed to store $n$ about $\log n$? –  froggie May 24 '12 at 1:13
3  
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
add comment

1 Answer

up vote 2 down vote accepted

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!)$.

share|improve this answer
    
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
1  
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.