Today I will offer you a nice algorithm, which, although it was invented quite recently (11 years ago), but the “prototype” was a counting device with a three-thousand-year history.

The authors

Sorting was presented in 2002 by three mathematicians from the University of Auckland in New Zealand: Joshua J. Arulanandham, Christian S. Calud (Cristian S. Calude) and Michael J. Dinin (Michael J. Dinneen). Scientists work in discrete mathematics, number theory, quantum computing, information theory, combinatorial algorithms.

I do not know which of the three belongs to the original idea. Perhaps Kaluda, who among other things teaches the history of computational mathematics. Everyone knows that the progenitor of accounts in Europe is an abacus , which migrated from Babylon to Egypt, from there to Greece, from it to Rome, from which it went all over Europe. The appearance and operation of the ancient “calculator” is so reminiscent of the behavior of this “simple” sort, that it is sometimes called “ Abacus sort ” (Abacus sort).
')

Algorithm

Suppose you need to sort a set of natural numbers . Under each other, each number is laid out in the form of a horizontal row of a corresponding number of balls. And now we will look at all these groups of balls not along horizontals, but along verticals . Shift the balls down until it stops. Again, switch to the horizontal and recalculate the beads in each row. Received the initial set of numbers, only ordered.

Implementation

Bead sort in 30+ programming languages ​​can be found here . Although visually the algorithm looks easier nowhere, from the point of view of software implementation, this is a very nontrivial sorting.

Degenerate case

This is a reverse-ordered array . The maximum possible number of balls will have to collapse from the highest points.

Limited applicability

The method is primarily applicable to natural numbers .

You can also sort integers, but this is more confusing - negative numbers will have to be processed separately from positive ones.

Nothing prevents you from sorting even fractional numbers if you first reduce them to integers (for example, multiply everything by 10 ^k , sort them, and then divide by 10 ^k ).

And, of course, even strings can be sorted, if each of them is represented as a positive integer. But why?

Time complexity

They are already sorting 4, depending on the context in which the algorithm is considered.

O (1)

Abstract case, spherical Bead sort in vacuum. If we imagine that all the moving balls simultaneously move and fall into place. This is an unrealizable complexity for this sorting - neither in the theory of algorithms, nor in practice.

O (√n)

An estimate for a physical model where the beads slide down the well-oiled spokes. Free fall time is proportional to the square root of the maximum height, which in turn is a multiple of n .

O (n)

Balls that have not yet reached their seats, amicably move one position down in one iteration. This complexity is appropriate to speak in the case of physical devices that implement this sorting method, analog or digital hardware implementations.

O (s)

S - the sum of the elements of the array. Each ball moves separately, rather than rolling a group of balls at the same time. Adequate complexity assessment for implementation in programming languages.

Memory difficulty

It leaves much to be desired. Bead sort is a record holder of extravagance - the cost of additional memory is many times higher than the cost of storing the array itself and on average is O (n ² ) .

Physics

The presence or absence of balls can be interpreted as an analog voltage passing through a series of electrical resistors. The rods through which the balls move are analogs of electrical resistors , the voltage in which increases from top to bottom.

Do not kick for the stupid use of electrical terms, in my school of physics there was a triple plus a four with a minus.

Connoisseurs of electrostatics refer for details in this pdf-document .

In fact

Bead sort is a sort of sorting by counting . The number of balls in each vertical track is the number of elements in the array that are equal or larger than the ordinal number of the vertical.

Algorithm Characteristics

Title	Beaded sorting (Bead sort); Abacus sort (Abacus sort)
The authors	Joshua J. Arulandanda, Christian S. Kalud, Michael J. Dinin
Year of publication	2002
Class	Sort by distribution
Resilience	Steady
Comparisons	No comparisons
Time complexity	O (1)	O (√n)	O (n)	O (s)
Memory difficulty	O (n 2 )

Links

Bead screening at the University of Auckland
Algorithm documentation, pdf
Implementation on various PL
Bead sort in English Wikipedia

Home pages of authors:

Joshua J. Arulanandham
Christian S. Kalud
Michael J. Dinin