Bead sort, also called gravity sort, is a natural sorting algorithm, developed by Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen in 2002, and published in The Bulletin of the European Association for Theoretical Computer Science. Both digital and analog hardware implementations of bead sort can achieve a sorting time of O(n); however, the implementation of this algorithm tends to be significantly slower in software and can only be used to sort lists of positive integers. Also, it would seem that even in the best case, the algorithm requires O(n2) space.
The bead sort operation can be compared to the manner in which beads slide on parallel poles, such as on an abacus. However, each pole may have a distinct number of beads. Initially, it may be helpful to imagine the beads suspended on vertical poles. In Step 1, such an arrangement is displayed using n=5 rows of beads on m=4 vertical poles. The numbers to the right of each row indicate the number that the row in question represents; rows 1 and 2 are representing the positive integer 3 (because they each contain three beads) while the top row represents the positive integer 2 (as it only contains two beads).
If we then allow the beads to fall, the rows now represent the same integers in sorted order. Row 1 contains the largest number in the set, while row n contains the smallest. If the above-mentioned convention of rows containing a series of beads on poles 1..k and leaving poles k+1..m empty has been followed, it will continue to be the case here.
The action of allowing the beads to "fall" in our physical example has allowed the larger values from the higher rows to propagate to the lower rows. If the value represented by row a is smaller than the value contained in row a+1, some of the beads from row a+1 will fall into row a; this is certain to happen, as row a does not contain beads in those positions to stop the beads from row a+1 from falling.
The mechanism underlying bead sort is similar to that behind counting sort; the number of beads on each pole corresponds to the number of elements with value equal or greater than the index of that pole.
Bead sort can be implemented with four general levels of complexity, among others:
- O(1): The beads are all moved simultaneously in the same time unit, as would be the case with the simple physical example above. This is an abstract complexity, and cannot be implemented in practice.
- O(): In a realistic physical model that uses gravity, the time it takes to let the beads fall is proportional to the square root of the maximum height, which is proportional to n.
- O(n): The beads are moved one row at a time. This is the case used in the analog and digital hardware solutions.
- O(S), where S is the sum of the integers in the input set: Each bead is moved individually. This is the case when bead sort is implemented without a mechanism to assist in finding empty spaces below the beads, such as in software implementations.
Like the Pigeonhole sort, bead sort is unusual in that in worst case it can perform faster than O(n log n), the fastest performance possible for a comparison sort in worst case. This is possible because the key for a bead sort is always a positive integer and bead sort exploits its structure.
This example is written in Python. The strategy for "dropping" the beads may be slightly different, but it does the same job.
1 def Gravity(obj): 2 if all([type(x) == int and x >= 0 for x in obj]): 3 ori = list(obj) #for original 4 ref = [range(x) for x in obj] #for reference 5 else: 6 raise ValueError("All elements must be positive integers") 7 inter =  #for intermediate 8 ind = 0 #for index 9 prev = sum([1 for x in ref if len(x) > ind]) #prev for previous 10 while prev: 11 inter.append(range(prev)) 12 ind += 1 13 prev = sum([1 for x in ref if len(x) > ind]) 14 ind = 0 15 prev = sum([1 for x in inter if len(x) > ind]) 16 out =  17 while prev: 18 out.append(prev) 19 ind += 1 20 prev = sum([1 for x in inter if len(x) > ind]) 21 out = out[::-1] 22 return out 23 24 """how it does it: it counts the "beads" in each column, then uses those numbers to make a new set of rows. 25 Adding up the beads in each column after turning the initial sums into the new rows gives the backwards 26 version of the sorted list, which is then turned around using list slicing. 27 If you believe you understand how the code does it and think you can describe it better, feel free to edit 28 this description. 29 Note: it might not work on zeroes, as the while loops stop when "prev" is equal to 0""" 30 # contributed by an amateur programmer. Feel free to test & use it.
References and notes
- By convention, a row representing the positive integer k should have beads on poles 1..k and poles k+1..m should be empty. This is not a strict requirement, but will most likely simplify implementation.