Algorithm Speed (2.00) :

Array Size (100) :

Bead Sort :

Author(s) : Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen Date : 2002

Bead sort, also known as gravity sort, is a natural sorting algorithm. It works by representing numbers as falling beads on vertical poles. When the beads fall, they naturally arrange themselves in sorted order. It is a conceptual algorithm that requires specialized hardware to achieve its theoretical O(1) time complexity, but in software, it typically runs in O(S) where S is the sum of the integers.

Time Complexity	O(S)
Best Case	O(n)
Worst Case	O(S)
Space Complexity	O(n²)
Stable	Unknown

def bead_sort(arr):
	if not arr:
		return []
	max_val = max(arr)
	beads = [[0] * len(arr) for _ in range(max_val)]
	for i, num in enumerate(arr):
		for j in range(num):
			beads[j][i] = 1
	for j in range(max_val):
		sum_beads = sum(beads[j])
		for i in range(len(arr)):
			beads[j][i] = 1 if i >= len(arr) - sum_beads else 0
	res = [0] * len(arr)
	for i in range(len(arr)):
		for j in range(max_val):
			res[i] += beads[j][i]
	return res

function beadSort(arr) {
	if (arr.length === 0) return [];
	let max = Math.max(...arr);
	let grid = Array.from({ length: max }, () => new Array(arr.length).fill(0));
	for (let i = 0; i < arr.length; i++) {
		for (let j = 0; j < arr[i]; j++) {
			grid[j][i] = 1;
		}
	}
	for (let j = 0; j < max; j++) {
		let sum = grid[j].reduce((a, b) => a + b, 0);
		for (let i = 0; i < arr.length; i++) {
			grid[j][i] = i >= arr.length - sum ? 1 : 0;
		}
	}
	let res = new Array(arr.length).fill(0);
	for (let i = 0; i < arr.length; i++) {
		for (let j = 0; j < max; j++) {
			res[i] += grid[j][i];
		}
	}
	return res;
}

public static int[] beadSort(int[] arr) {
	if (arr.length == 0) return new int[0];
	int max = arr[0];
	for (int i = 1; i < arr.length; i++) {
		if (arr[i] > max) max = arr[i];
	}
	int[][] grid = new int[max][arr.length];
	for (int i = 0; i < arr.length; i++) {
		for (int j = 0; j < arr[i]; j++) {
			grid[j][i] = 1;
		}
	}
	for (int j = 0; j < max; j++) {
		int sum = 0;
		for (int i = 0; i < arr.length; i++) sum += grid[j][i];
		for (int i = 0; i < arr.length; i++) {
			grid[j][i] = i >= arr.length - sum ? 1 : 0;
		}
	}
	int[] res = new int[arr.length];
	for (int i = 0; i < arr.length; i++) {
		for (int j = 0; j < max; j++) {
			res[i] += grid[j][i];
		}
	}
	return res;
}

func beadSort(arr []int) []int {
	if len(arr) == 0 {
		return []int{}
	}
	max := arr[0]
	for _, v := range arr {
		if v > max {
			max = v
	}
	}
	grid := make([][]int, max)
	for i := range grid {
		grid[i] = make([]int, len(arr))
	}
	for i, v := range arr {
		for j := 0; j < v; j++ {
			grid[j][i] = 1
		}
	}
	for j := 0; j < max; j++ {
		sum := 0
		for i := 0; i < len(arr); i++ {
			sum += grid[j][i]
		}
		for i := 0; i < len(arr); i++ {
			if i >= len(arr)-sum {
				grid[j][i] = 1
			} else {
				grid[j][i] = 0
			}
		}
	}
	res := make([]int, len(arr))
	for i := 0; i < len(arr); i++ {
		for j := 0; j < max; j++ {
			res[i] += grid[j][i]
		}
	}
	return res
}

void beadSort(int *arr, int len) {
	int i, j, max, sum;
	unsigned char *grid;
	for (i = 1, max = arr[0]; i < len; i++) {
		if (arr[i] > max) max = arr[i];
	}
	grid = calloc(1, max * len);
	for (i = 0; i < len; i++) {
		for (j = 0; j < arr[i]; j++) {
			grid[j * len + i] = 1;
		}
	}
	for (j = 0; j < max; j++) {
		for (sum = i = 0; i < len; i++) {
			sum += grid[j * len + i];
		}
		for (i = 0; i < len; i++) {
			grid[j * len + i] = i >= len - sum ? 1 : 0;
		}
	}
	for (i = 0; i < len; i++) {
		for (j = 0, arr[i] = 0; j < max; j++) {
			arr[i] += grid[j * len + i];
		}
	}
	free(grid);
}