↩ back to Non-Comparison Sorts
This site's other nine Non-Comparison Sorts — counting sort, radix sort, American flag sort, bucket sort, pigeonhole sort, Flash Sort, Spreadsort, Proxmap sort, and MSD string sort — all get their speed the same way: extract structure from the values themselves (a digit, a bucket index, a count) with arithmetic instead of comparisons. Bead sort does something stranger: it doesn't touch the values arithmetically at all. It represents each number physically, as a row of beads threaded on vertical rods, then lets gravity settle them. No digit extraction, no bucket boundaries — the sort is a side effect of beads falling as far down as they can.
Enter a comma-separated list of non-negative integers (bead sort has no way
to represent a negative count of beads — see Pitfalls). Each row i
gets a bead in column j whenever arr[i] > j — beads pushed flush against
the left wall, like an abacus. Press Step or Run to watch gravity
settle the grid one column at a time: for each column, count how many rows currently have a bead in
it, then pack that many beads into the bottom rows of that column and clear the rest. Once
every column has settled, each row's bead count — read top to bottom — is the sorted array.
Every column settles independently — column j only cares how
many of the n rows currently have a bead in it, call that count c. After
gravity, the bottom c rows have a bead in column j and the top
n − c rows don't; which specific rows contributed the original beads is irrelevant,
only the count. That's the whole mechanism, repeated once per column. Why does repeating it
column-by-column produce a globally sorted result, instead of just shuffling beads within each
column separately? Because a row that ends up with a bead in column j after settling
is, by construction, one of the c largest-bead-count rows among that column's own
contributors — and every earlier column's settling already pushed the largest values toward
the bottom too. The columns aren't independent of each other in effect, only in mechanism: each one
reinforces the same bottom-loaded ordering the previous columns already started building, so by the
time the last column settles, row n−1 (bottom) holds the largest value and row
0 (top) holds the smallest, with every row in between non-decreasing top to bottom.
This doesn't depend on which original row held which value. Load the demo's default array
3, 1, 4, 1, 5 and separately 5, 1, 4, 1, 3 — same multiset, different
row order — and the settled grid produces the identical output 1, 1, 3, 4, 5 either
way. That's not a coincidence; it's the direct consequence of each column only ever counting, never
tracking which row a bead belonged to. It's also why bead sort can only ever produce a
sorted list of values, never a stably-reordered list of records — see Pitfalls.
This is the exact scheme the demo above steps through, one column at a time:
function beadSort(arr) {
const n = arr.length;
if (n === 0) return [];
const cols = Math.max(...arr, 0);
// grid[i][j] = true iff row i has a bead in column j
const grid = arr.map(v => Array.from({ length: cols }, (_, j) => j < v));
for (let j = 0; j < cols; j++) {
const count = grid.reduce((s, row) => s + (row[j] ? 1 : 0), 0);
for (let i = 0; i < n; i++) grid[i][j] = i >= n - count; // pack into bottom `count` rows
}
return grid.map(row => row.reduce((s, bead) => s + (bead ? 1 : 0), 0));
}Grid width tracks the largest value, not the value spread. Counting sort
handles a wide-but-clustered range like [1000, 1001, 1002] cheaply, by offsetting
every value down by min so its bucket array only needs 3 slots. Bead sort has no
equivalent trick: a bead count is a physical, non-negative quantity, so a value of 1002
needs 1002 columns no matter how close the other values sit to it. The same array that
costs counting sort O(n+3) costs bead sort O(n·1002). Whenever values are
large but tightly clustered, bead sort is the wrong tool.
An off-by-one on the column count silently drops the top of the range. The
demo's checkbox reproduces a real bug: allocate max − 1 columns instead of
max. On the default array 3, 1, 4, 1, 5 (correct output
1, 1, 3, 4, 5), dropping the last column caps every row at 4 beads — the row holding
5 can never get more than max − 1 = 4 beads, so it comes out indistinguishable
from the row holding 4. The demo's own generator, run with the checkbox on, produces
1, 1, 3, 4, 4 — a value silently lost, not a crash, which is exactly what makes an
off-by-one like this dangerous: the output still looks sorted.
Negative numbers have no representation at all. Counting sort's bucket-index offset handles negatives for free; there's no equivalent for bead sort, because a rod can't hold a negative number of beads. This demo rejects negative input outright rather than pretending to handle it.
It can't carry along a record's other fields. Every sort elsewhere on this site
that discusses stability is asking "when two
elements tie on the sort key, does the one that came first in the input stay first in the output?"
Bead sort can't even ask that question: as the "Why it works" section above demonstrates, the
settled grid never records which original row contributed which bead, only how many. Given a list
of (key, payload) records, bead sort can tell you the sorted keys, but not
which payload belongs with which key in that sorted order — the identity is gone the moment gravity
settles the first column.
Time: O(n·max) in this software simulation — for each of up to
max columns, one pass over all n rows to count, and one pass to reassign.
Space: O(n·max) for the grid itself. Bead sort's original point isn't
this simulated bound, though — it's a natural algorithm
(Arulanandham, Calude & Dinneen, 2002): built as actual beads on actual rods under actual
gravity, every column settles simultaneously, in parallel, in whatever time
physical beads take to fall — no per-column loop at all. That's a genuinely different machine model
than the sequential JavaScript this page steps through, and this page makes no claim to have built
that hardware; the O(n·max) above is what the loop above actually does, not what
gravity itself could do.
See Choosing a Non-Comparison Sort for how this compares against the site's other nine Non-Comparison Sorts entries — short version: reach for this only when the natural-algorithm model itself is the point, not when sorting non-negative integers in software.