Spaghetti sort

Schematic diagram of spaghetti sorting. The spaghetti can be sorted by removing them from the bundle on the table in the order they stick out.

Spaghetti sort is a linear-time, analog algorithm for sorting a sequence of items, introduced by A. K. Dewdney in his Scientific American column.[1][2][3] This algorithm sorts a sequence of items requiring O(n) stack space in a stable manner. It requires a parallel processor.

  1. ^ Dewdney, A. K. (June 1984), "On the spaghetti computer and other analog gadgets for problem solving", Scientific American, vol. 250, no. 6, pp. 19–26
  2. ^ Stauffer, Dietrich (May 15, 1999), Annual Reviews of Computational Physics VI, World Scientific, p. 260, ISBN 981-02-3563-1
  3. ^ Adamatzky, Andrew (July 1, 2006), From Utopian to Genuine Unconventional Computers, Luniver Press, p. 96, ISBN 0-9551170-9-7