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.^[1]^[2]^[3] This algorithm sorts a sequence of items requiring O(n) 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(1) time.

^ 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
^ Stauffer, Dietrich (May 15, 1999), Annual Reviews of Computational Physics VI, World Scientific, p. 260, ISBN 981-02-3563-1
^ Adamatzky, Andrew (July 1, 2006), From Utopian to Genuine Unconventional Computers, Luniver Press, p. 96, ISBN 0-9551170-9-7

[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

[1]

[2]

[3]

Spaghetti sort

From Wikipedia, the free encyclopedia · View on Wikipedia