Hacker News Reader

Comment by linsomniac | Hacker News Reader

>you can let the world do the work for you.

Reminds me of the Spaghetti Sorting algorithm. https://en.wikipedia.org/wiki/Spaghetti_sort

Spaghetti Sorting is just one of the Analog Gadgets called out in Dewdney's "The Armchair Universe" (originally in his Computer Recreations column in "Scientific American"). There are many other cool ones (beginning on page 28):

https://archive.org/details/armchairuniverse0000dewd_x2e7/

Interesting but I am not sure I understand this:

>> contact-and-removal operation takes constant time, the worst-case time complexity of the algorithm is O(n).

How is the contact-and-removal operation constant time? How can that assumption ever be true? If you use a parallel processor like human vision or human feel (ie. which pressure nerve activates on the hand) it may appear constant, but if you use a computer it would be n right (as you would need to check n slots). Wouldn't either defy O(n)?

The analog algorithm described is not described for digital computer. It’s an amusing theoretical thought experiment and not a recipe for actual fast sorting. It’s O(n) when you use your hand for contact and removal. I don’t know if it’s possible to implement spaghetti sort on a computer, maybe not, but I guess if it were possible, it would probably at least require n processors to sort n elements. Maybe the nearest analogy on digital computers is radix sort.

Radix sort is probably the closest usable one, but a more direct translation would probably be sleep sort.

Oh yeah I forgot about sleep sort, that is similar and also more in the same spirit as spaghetti sort. ;)

Depends on the mathematical framework you're working with.... there's a genre in theoretical compsci that deals with parallel algorithms, and as a toy example, I remember an O(1) sorting algo (given O(n^2) processors). This example is more fun than anything, but ofc in general you're free what constraints you subject your statements to.

You can simplify the "human hand" to a rigid metal sheet that comes down from the top and stops on the highest object. Still constant time, but no "parallel processing" needed.

The point is that reality itself is highly parallel

I wonder if the removal operation is not actually O(sqrt(n)). Depending on the way we structure thought experiment of course. But as the pile of spaghetti gets bigger, the act of picking the largest one is constrained by:

1. how fast your hand can reach for the next spaghetti piece - on average proportional to the radius of the pile of spaghetti, which is proportional to sqrt(n).

2. to actually notice the biggest piece, you need to again wait for a time proportional to sqrt(n) - light propagation is not instant.

So if we start thinking about this algorithm more like a computer scientist would (how fast it is as n grows to the infinity) it doesn't seem to be O(n) IMO.

You're talking about some other kind of sort.

That's how some 'trick' card decks work, for anyone unfamiliar

Of course, all computation is just setting up some physical stuff in such a way that, after the laws of physics play themselves out for a while, that physical stuff will be in a new state, and you'll be able to interpret your desired result from that new state.

Reply on news.ycombinator.com