[Solved]: Sorting numbers in $O(1)$

Problem Detail: 

Here is an experiment I came up with (I don't have sufficient material to make it):

Say that, you have a list of $n$ numbers $L = \{l_1, l_2, ..., l_n\}$.
And you have bars representing those numbers like so:

Say that, width of every bar is $w$.
Imagine a line, thatis made up of $n$ line segments, each of them are $w$ long, and they are enough to cover all the bars.
When any of the lines touches a bar, it sends a signal, declaring its ID.
ID of each bar correspods to its position.

If we are able to build a system as described above, we can release the whole line and store the signals respectively in an array, therefore have the real poisitons of each number we want to sort.

Therotically, when does it take more time and energy to sort $n$ numbers with this method than sorting $n$ numbers using a supercomputer?

Asked By : cagirici

Answered By : Yuval Filmus

This is similar to what is known as counting sort. Whether your method is more efficient than other methods depends on the model of computation, which you haven't specified. For example, what if the dynamic range of the numbers is really large, say they are integers from $0$ to $2^{100}$? You could use some adaptive approach ("scanning" from top to bottom, stopping each time a number is reached), but it really depends on what your computer is allowed to do, and in practice you probably won't be able to pull it off. Counting sort is a conventional algorithm which uses a very similar idea in situations in which the dynamic range is small, in which case the algorithm is highly effective.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/26133

 Ask a Question

 Download Related Notes/Documents