3
$\begingroup$

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:

enter image description here

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?

$\endgroup$
  • 3
    $\begingroup$ This is called spaghetti sort, because you can do it with uncooked spaghetti noodles where noodle $i$ is cut to length $l_i$. But it's $O(N)$ (at best) because you have to cut and label each piece of spaghetti and then you have to pull them out of the bundle one-by-one longest to shortest. $\endgroup$ – Wandering Logic May 27 '14 at 1:08
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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