Bead sort, also named 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 analogue 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.

COMING SOON!

```
"""
Bead sort only works for sequences of nonegative integers.
https://en.wikipedia.org/wiki/Bead_sort
"""
def bead_sort(sequence: list) -> list:
"""
>>> bead_sort([6, 11, 12, 4, 1, 5])
[1, 4, 5, 6, 11, 12]
>>> bead_sort([9, 8, 7, 6, 5, 4 ,3, 2, 1])
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> bead_sort([5, 0, 4, 3])
[0, 3, 4, 5]
>>> bead_sort([8, 2, 1])
[1, 2, 8]
>>> bead_sort([1, .9, 0.0, 0, -1, -.9])
Traceback (most recent call last):
...
TypeError: Sequence must be list of nonnegative integers
>>> bead_sort("Hello world")
Traceback (most recent call last):
...
TypeError: Sequence must be list of nonnegative integers
"""
if any(not isinstance(x, int) or x < 0 for x in sequence):
raise TypeError("Sequence must be list of nonnegative integers")
for _ in range(len(sequence)):
for i, (rod_upper, rod_lower) in enumerate(zip(sequence, sequence[1:])):
if rod_upper > rod_lower:
sequence[i] -= rod_upper - rod_lower
sequence[i + 1] += rod_upper - rod_lower
return sequence
if __name__ == "__main__":
assert bead_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
assert bead_sort([7, 9, 4, 3, 5]) == [3, 4, 5, 7, 9]
```