# Bead Sort

# Bead Sort

Bead sort, also called gravity sort, sorts non-negative integers by simulating beads falling under gravity. Each number is represented as a column of beads, and beads “fall” downward to form a sorted arrangement.

The model relies on a physical analogy rather than comparisons.

## Problem

Given a sequence $A$ of non-negative integers, reorder it such that

$$
A[0] \le A[1] \le \cdots \le A[n-1]
$$

## Representation

Each value $A[i] = k$ is represented by $k$ beads in row $i$, aligned to the left:

Example:

$$
A = [5, 3, 1]
$$

Bead grid:

```
● ● ● ● ●
● ● ●
●
```

## Algorithm

1. Represent each number as a row of beads
2. Let beads fall vertically (columns collapse downward)
3. Count beads in each row after falling

```id="k2x9p1"
bead_sort(A):
    if A is empty:
        return

    max_val = max(A)
    grid = matrix of size n x max_val

    for i from 0 to n - 1:
        for j from 0 to A[i] - 1:
            grid[i][j] = 1

    for j from 0 to max_val - 1:
        sum = 0
        for i from 0 to n - 1:
            sum += grid[i][j]
            grid[i][j] = 0

        for i from n - sum to n - 1:
            grid[i][j] = 1

    for i from 0 to n - 1:
        A[i] = count of beads in row i
```

## Example

Let

$$
A = [5, 3, 1]
$$

Initial grid:

```
● ● ● ● ●
● ● ●
●
```

After gravity:

```
●
● ●
● ● ●
● ● ● ● ●
```

Final array:

$$
[1, 3, 5]
$$

## Correctness

Each column independently accumulates beads at the bottom. After all columns settle, rows represent increasing bead counts from top to bottom. This corresponds to sorting the original values in ascending order.

## Complexity

| case    | time                |
| ------- | ------------------- |
| general | $O(n \cdot \max A)$ |

Space complexity:

$$
O(n \cdot \max A)
$$

## Constraints

* Only works for non-negative integers
* Requires discrete representation of values
* inefficient for large values

## Properties

* not comparison-based
* not stable
* uses physical analogy
* highly memory dependent

## When to Use

Bead sort is mainly of theoretical and educational interest. It demonstrates how physical processes can model computation. It is impractical for large inputs or large values.

## Implementation

```id="m8x2q3"
def bead_sort(a):
    if not a:
        return a

    max_val = max(a)
    n = len(a)

    grid = [[0] * max_val for _ in range(n)]

    for i in range(n):
        for j in range(a[i]):
            grid[i][j] = 1

    for j in range(max_val):
        count = 0
        for i in range(n):
            count += grid[i][j]
            grid[i][j] = 0

        for i in range(n - count, n):
            grid[i][j] = 1

    for i in range(n):
        a[i] = sum(grid[i])

    return a
```

```id="z4k7v2"
func BeadSort(a []int) {
    if len(a) == 0 {
        return
    }

    maxVal := 0
    for _, v := range a {
        if v > maxVal {
            maxVal = v
        }
    }

    n := len(a)
    grid := make([][]int, n)
    for i := range grid {
        grid[i] = make([]int, maxVal)
    }

    for i := 0; i < n; i++ {
        for j := 0; j < a[i]; j++ {
            grid[i][j] = 1
        }
    }

    for j := 0; j < maxVal; j++ {
        count := 0
        for i := 0; i < n; i++ {
            count += grid[i][j]
            grid[i][j] = 0
        }

        for i := n - count; i < n; i++ {
            grid[i][j] = 1
        }
    }

    for i := 0; i < n; i++ {
        sum := 0
        for j := 0; j < maxVal; j++ {
            sum += grid[i][j]
        }
        a[i] = sum
    }
}
```