The bead sort algorithm operates by visualizing the elements of a list as beads arranged on vertical rods.

Bead sort, also referred to as gravity sort, is a natural sorting algorithm that functions as both a distribution sort and a comparison sort. However, it is important to note that it is not a stable sorting algorithm. The method conceptualizes the elements of the list as beads on vertical rods, where each bead represents a single unit. The rods are then “shaken,” allowing the beads to fall down and stack on top of one another. The resulting height of each stack corresponds to the sorted order of the list.

The algorithm begins by mapping each element of the input list to a rod, where the height of each rod reflects the value of the corresponding element. Following this mapping, the rods are “shaken” (figuratively), causing the beads to cascade to the bottom. The beads accumulate in stacks, with taller stacks forming on the left and shorter stacks on the right. This process continues until all beads have settled. The heights of the stacks are then read to produce the sorted list.

Bead sort can be implemented using either arrays or linked lists. In an array implementation, the array is traversed from left to right, with each element replaced by a representation of beads (typically denoted as $1$s). Subsequently, the array is “shaken” by summing the heights of the columns and updating the original array with these sums. In a linked list implementation, each node contains a counter and a pointer to the next node. The list is traversed, and for each node, a new node is created with a counter equal to the value of the current node. This new node is then inserted into the sorted list at the appropriate position.

While bead sort is a straightforward and intuitive algorithm, it is rarely used in practical applications due to its poor time complexity. The time complexity of bead sort is $O(n^2)$, which makes it inefficient for sorting large lists. Nonetheless, it can be beneficial for educational purposes, as it offers a clear visualization of the sorting process.