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. Implementation This implementation is written in the Python; it is assumed that the 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. def beadsort(input_list): """Bead sort.""" return_list = [] # Initialize a 'transposed list' to contain as many elements as # the maximum value of the input -- in effect, taking the 'tallest' # column of input beads and laying it out flat transposed_list = [0] * max(input_list) for num in input_list: # For each element (each 'column of beads') of the input list, # 'lay the beads flat' by incrementing as many elements of the # transposed list as the column is tall. # These will accumulate atop previous additions. transposed_list[:num] = [n + 1 for n in transposed_list[:num]] # We've now dropped the beads. To de-transpose, we count the # 'bottommost row' of dropped beads, then mimic removing this # row by subtracting 1 from each 'column' of the transposed list. # When a column does not reach high enough for the current row, # its value in transposed_list will be <= 0. for i in range(len(input_list)): # Counting values > i is how we tell how many beads are in the # current