{"document_url": "https://en.wikipedia.org/wiki/Bead_sort"}
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.

Algorithm overview
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.

Correctness

We can prove by induction that Bead-sort is correct.

To prove that the algorithm works correctly, we can use the following steps:
To do this, we can assume that the first
beads are already sorted correctly. We can then add the
bead to the set of beads, and the bead will slide down to the appropriate position based on its value.

If the
bead is less than or equal to the
bead, it will settle at the same barrier as the
bead. This ensures that the first
beads are sorted correctly.

If the
bead is larger than the
bead, it will slide past the
bead and settle at the next barrier. However, since the first
beads are already sorted correctly, the
bead must be larger than all of the first
beads. Therefore, it must settle at a barrier beyond the
bead, and the first
beads are sorted correctly.

Since the base case is satisfied and the inductive step holds, the algorithm is correct for any number of beads.

In conclusion, we have shown by induction that Bead-sort is correct. Each step of the algorithm sorts a single bead correctly, and the correct placement of each bead ensures that the entire set of beads is sorted correctly.

Complexity

Bead sort can be implemented with four general levels of complexity, among others:
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.

Implementation

This implementation is written in the Python; it is assumed that the input_list will be a sequence of integers. The function returns a new list rather than mutating the one passed in, but it can be trivially modified to operate in place efficiently.

We can also implement the algorithm using Java.