gravity_sort.py

def beadsort(input_list: list[int]):
    """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.
    input_length = len(input_list)
    for i in range(input_length):
        # Counting values > i is how we tell how many beads are in the
        # current 'bottommost row'. Note that Python's bools can be
        # evaluated as integers; True == 1 and False == 0.
        bead_sum = 0
        for n in transposed_list:
            if n >= input_length - i:
                bead_sum += 1
        return_list.append(bead_sum)
    # The resulting list is sorted in descending order
    return return_list

array = [4, 3, 8, 2, 1]
print(array)
sorted_array = beadsort(array)