sort n numbers in the range [0,1] without multiplying or dividing

Question

Given an array with n real numbers, each in the range [0,1], I need to sort them. Moreover, the only operations that are allowed are comparisons or copying.

It means I cannot multiply or divide the numbers, which prohibits me from using bucket sort.

From what I learned, when you use only comparisons you cant sort any faster that O(nlogn). That means that I can just use any sort algorithm that achieves this bound, let's say heapsort, and be done with it.

However, in this way i don't use the info that the numbers are from the range [0,1]. For this reason, I'm not sure if I'm right.

Answer 1

The $\Omega(n \log n)$ lower bound still applies; you still can't do better than $O(n \log n)$.

(Proof: Take any array of numbers. You can find the maximum and minimum in $O(n)$ time. Then, rescale the array. In particular, if the minimum and maximum are $\alpha$ and $\beta$, replace each element $x$ of the array with $(x-\alpha)/(\beta-\alpha)$. After the replacement, every element will be in the range $[0,1]$. If you had a way to sort such arrays faster than $O(n \log n)$, you'd immediately obtain a way to sort the original array faster than $O(n \log n)$.)

Answer 2

You can find the proof in TAOCP - there are n! (i.e. factorial of n) of possible orderings. Since each comparison returns only single bit of information and thus only halves amount of possibilities, you need to perform at least log(n!) comparisons which is O(n log n).

Of course, the same proof applies to the radix sort ;) The real difference between comparison-based sorts and radix is that you can reveal more than one bit of info by a single choose_bucket operation.

The rest is just subtle difference of initial conditions - you can sort with comparisons faster than O(n log n) given sufficient amount of duplicates. And you cannot sort with radix faster than O(n log n) if all sorted values are unique.

In your particular case, do you mean theoretical unilimited-precision floating numbers? In this case, you cannot sort them with a fixed prescribed amount of radix sort passes. OTOH, if you mean real-world fixed size FP values, they can be sorted with a fixed amount of comparisons per array element although, well, this amount is pretty large ;)