Spaghetti sort

Spaghetti sort is a linear-time, analog algorithm for sorting a sequence of items, introduced by A. K. Dewdney in his Scientific American column. For a list of natural numbers, a rod of uncooked spaghetti is prepared with a length matching each number. The rods are held loosely in a fist and lowered so that they all stand upright on a table, and a flat hand lowered from above meets the longest rod first. That rod is removed and placed at the front of the output list, and the step is repeated until no rods remain, which yields the sorted sequence. Preparing the rods takes linear time, and lowering them takes constant time because the hand, the rods and the table act as a fully parallel computing device, so the source gives a worst-case time of O(n). The sort is stable and needs O(n) stack space, but it requires a parallel processor that is assumed able to find the maximum of a sequence in constant time, so it is a thought experiment about physical models of computation rather than a practical program.