Bead Sort

Bead sort, also known as gravity sort, is a natural sorting algorithm, developed by Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen in 2002. Both digital and analog hardware implementations of bead sort can achieve a sorting time of O(n); however, the implementation of this algorithm tends to be significantly slower in software and can only be used to sort lists of positive integers. Also, it would seem that even in the best case, the algorithm requires O(n2) space.

									Public Shared Sub BeadSort(ByRef data As Integer())
	Dim i As Integer, j As Integer, max As Integer, sum As Integer
	Dim beads As Byte()

	i = 1
	max = data(0)
	While i < data.Length
		If data(i) > max Then
			max = data(i)
		End If
		i += 1
	End While

	beads = New Byte(max * data.Length - 1) {}

	For i = 0 To data.Length - 1
		For j = 0 To data(i) - 1
			beads(i * max + j) = 1
		Next
	Next

	For j = 0 To max - 1
		sum = 0
		i = 0
		While i < data.Length
			sum += beads(i * max + j)
			beads(i * max + j) = 0
			i += 1
		End While

		For i = data.Length - sum To data.Length - 1
			beads(i * max + j) = 1
		Next
	Next

	For i = 0 To data.Length - 1
		j = 0
		While j < max AndAlso Convert.ToBoolean(beads(i * max + j))


			j += 1
		End While
		data(i) = j
	Next
End Sub

Example

									Dim data As Integer() = {586, 25, 58964, 8547, 119, 0, 78596}
BeadSort(data)

Output