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. This algorithm sorts a sequence of items requiring O stack space in a stable manner. It requires a parallel processor, which is assumed to be able to find the maximum of a sequence of items in O time.

Algorithm

For simplicity, assume we are sorting a list of natural numbers. The sorting method is illustrated using uncooked rods of spaghetti:
  1. For each number x in the list, obtain a rod of length x.
  2. Once you have all your spaghetti rods, take them loosely in your fist and lower them to the table, so that they all stand upright, resting on the table surface. Now, for each rod, lower your other hand from above until it meets with a rod—this one is clearly the longest. Remove this rod and insert it into the front of the output list. Repeat until all rods have been removed.

Analysis

Preparing the n rods of spaghetti takes linear time. Lowering the rods on the table takes constant time, O. This is possible because the hand, the spaghetti rods and the table work as a fully parallel computing device. There are then n rods to remove so, assuming each contact-and-removal operation takes constant time, the worst-case time complexity of the algorithm is O.