Bead sort

Bead Sort[1] is a natural sorting algorithm, developed by Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen in 2002 at the Department of Computer Science - University of Auckland[2], New Zealand.

The Bead Sort Paper [3] was published in The Bulletin of the European Association for Theoretical Computer Science 76 (2002), 153-162.

Why Natural?

The term "Natural Algorithm" is explained by the authors in the abstract of the paper: "Nature is not only a source of minerals and precious stones but is also a mine of algorithms. By observing and studying natural phenomena, computer algorithms can be extracted."

Why is this algorithm interesting?

The excellence of this algorithm follows from the fact that it manages to beat the O(nlogn) lower bound for sorting that cannot be beaten by any sequential machine. The Bead Sort Algorithm manages to do its job in O(n) (or even in Big O of square root of n, depending on how we choose to analyze/implement it).

Beads and rods plus the work of gravity

The algorithm represents the positive integers by a set of beads, like those used in an abacus. Beads are attached to vertical rods and appear to be suspended in the air just before sliding down (a number is read horizontally, as a row). After their fall, the rows of numbers have been rearranged such that the smaller numbers appears on top of greater numbers.

Since representing very large lists using physical beads is, of course, impractical, the paper also describes a number of hardware implementations which directly represent the beads and simulate their falling behavior in a highly parallelized manner.

References, Links & Resources

(1) The Bead Sort Paper [4]

(2) A Graphic Gallery [5]

(3) Bead Sort on Math World [6]