# 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?

-

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

## 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 Narain 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
@Marvis: When we're counting the $\log n$ cost for Radix sort, we really should also be counting the $\log n$ cost to read/write numbers for a comparison-based sort, as well as the $\log n$ cost to do a compare. Despite your statement, radix sort doesn't do any comparisons -- instead, it can be viewed as breaking comparison apart into its component operations down into its component operations, and working with those in a more efficient way than a comparison-based sort could. – Hurkyl May 24 '12 at 1:50
show 2 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 37, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9425100088119507, "perplexity_flag": "middle"}