Bead Sort (Gravity Sort): Mechanism, Complexity Analysis & Interactive Visualizer

Bead Sort (Gravity Sort)

A natural sorting algorithm: represents numbers as rows of sliding beads on vertical wires, letting gravity pull the beads down to sort the items instantly in analog hardware.

How it works

Bead Sort (Gravity Sort), designed by Joshua J. Arulanandham, Cristian S. Calude, and Michael J. Dinneen in 2002, is a natural algorithm that mimics physics. Conceptually, it uses an abacus-like grid of vertical wires and horizontal sliding beads:

1. Bead Representation: Each positive integer in the input is represented by a row of beads. For example, the number \(3\) is represented by \(3\) beads on a row (from left to right).
2. Gravity Action: The wires are held vertically, allowing all beads to slide down under gravity. Because of this, rows containing fewer beads will let beads drop past them, and beads will stack up from the bottom.
3. Sorted Values: Once the beads have settled, the number of beads on each horizontal row represents the sorted values of the original list.

Complexity

Interactive visualization

Pseudocode

procedure beadSort(A):
  n ← length(A)
  maxVal ← findMax(A)
  
  grid ← 2D array of size n × maxVal filled with 0
  
  for i from 0 to n - 1:
    for j from 0 to A[i] - 1:
      grid[i][j] ← 1
      
  # Let beads drop
  for j from 0 to maxVal - 1:
    beadsCount ← 0
    for i from 0 to n - 1:
      beadsCount ← beadsCount + grid[i][j]
      grid[i][j] ← 0
      
    for i from n - beadsCount to n - 1:
      grid[i][j] ← 1
      
  # Reconstruct sorted array
  for i from 0 to n - 1:
    sum ← 0
    for j from 0 to maxVal - 1:
      sum ← sum + grid[i][j]
    A[i] ← sum

JavaScript implementation

function beadSort(arr) {
  const n = arr.length;
  if (n <= 1) return arr;
  
  let max = arr[0];
  for (let x of arr) {
    if (x > max) max = x;
  }
  
  // grid[i][j] represents bead on row i, wire j
  const grid = Array.from({ length: n }, () => new Array(max).fill(0));
  
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < arr[i]; j++) {
      grid[i][j] = 1;
    }
  }
  
  for (let j = 0; j < max; j++) {
    let count = 0;
    for (let i = 0; i < n; i++) {
      count += grid[i][j];
      grid[i][j] = 0;
    }
    for (let i = n - count; i < n; i++) {
      grid[i][j] = 1;
    }
  }
  
  for (let i = 0; i < n; i++) {
    let sum = 0;
    for (let j = 0; j < max; j++) {
      sum += grid[i][j];
    }
    arr[i] = sum;
  }
  return arr;
}

Pros and cons

When (not) to use it

• Physical/Hardware systems: Highly effective in optical computing or dedicated FPGA chips that can model parallel wires and gravity.
• Traditional software: Never use Bead Sort in digital software development. The space and time requirements degrade rapidly as the maximum element size increases.