Bead Sort

Average time complexity - O(2n^2)

Best-Case time complexity - Ω(4n)

Worst-Case time complexity - O(3n^2)

Worst-case space complexity - Ω(n^2)

Gravity Sort, also known as Bead Sort, is a sorting algorithm based on the abacus. It is theoretically fast because you would only drop the beads into their positions, but in practice it is quite slow because it is implemented on a single thread and it consumes a lot of memory.

The algorithm is quite complicated. It creates a two-dimensional grid of the items, and then lets items 'fall' into place.

Take the following array:

4, 1, 7, 2, 3

Gravity Sort creates a two-dimensional abacus from this. The number of beads in a row relates to the value of the item in that row.:

• 4 4 4 4
• 1
• 7 7 7 7 7 7 7
• 2 2
• 3 3 3

It then lets the beads 'fall' into place. Let's go through it from bottom to top.

First the two third, fourth, fifth, and sixth 7s on the third row fall down to the bottom:

• 4 4 4 4
• 1
• 7 7 7
• 2 2
• 3 3 3 7 7 7 7

Next the third 7 falls down one level to the second row from the bottom.

• 4 4 4 4
• 1
• 7 7
• 2 2 7
• 3 3 3 7 7 7 7

Next the fourth 4 falls down to the second from the bottom row.

• 4 4 4
• 1
• 7 7
• 2 2 7 4
• 3 3 3 7 7 7 7

Next the third 4 falls down two rows to the middle row.

• 4 4
• 1
• 7 7 4
• 2 2 7 4
• 3 3 3 7 7 7 7

Next the second 4 falls down one row.

• 4
• 1 4
• 7 7 4
• 2 2 7 4
• 3 3 3 7 7 7 7

The abacus is now complete. The algorithm now counts the number of elements in each row.

The first row has one element. The second row has two elements. The third row has three elements. The fourth row has four elements. The fifth row has seven elements.

1, 2, 3, 4, 7

This abucus works in all situations with the set of natural numbers.