2018-12-15:
Spaghetti sort
Spaghetti sort is an analog algorithm for sorting a sequence of numbers in linear time. This means that when you double the amount of numbers to be sorted, the time needed to sort those numbers only doubles, as well. That's a highly unusual property, with usual sorting algorithm becoming more and more less efficient the more numbers there are to be sorted.
The algorithm goes like this:
- For each number, break off a piece of spaghetti, whose length equals the number. This takes linear time.
- Take all spaghetti in your fist, and slam their lower sides on the table, so they all point up starting at the table. This takes constant time, thanks to the multi-processing properties of our universe.
- Lower your other hand on the bundle of spaghetti. Take out the one which you touch first. This is clearly the longest one. Continue to lower your hand and to remove spaghetti, laying them out next to each other, until all spaghetti have been processed. Again, this takes linear time.
- Transcribe the spaghetti lengths back to the respective numbers, using linear time. Done!
This algorithm was introduced by Canadian scientist Alexander Dewdney in his Scientific American colum.