Abacus Sort

Introduction

Abacus sort is an O(n) (linear time) sorting algorithm. It works most naturally for non-negative integers, but can be extended to real numbers.

Algorithm Description

Abacus sort is most easily described in an analogue fashion. Represent each of the initial n numbers to be sorted by its binary representation and then "stack" the numbers on to vertical abacus rods by placing a bead to represent 1 and leaving a gap to represent 0. This requires a total of ceiling(log₂ N) rods, where N is the maximum of the numbers to be sorted. The least significant rod represents 2⁰ and the most significant rod represents 2^k, the highest power of 2 less than or equal to N.

Then allow the beads to fall down the rods, so that each rod contains a stack of beads with no gaps in it. Read off the binary value of the bottom row of beads - this is the largest of the numbers. Continue reading binary values up the rods, until n values have been read - the last value is the smallest of the numbers (it may be zero).

Analysis

Encoding the binary numbers takes O(n) time. Letting the beads fall takes constant time. Decoding the sorted binary numbers takes O(n) time. Overall, the algorithm is O(n).

Since each bead represents the same binary digit before and after the sorting operation, the sum of the values represented by the bits does not change. Therefore, the sum of the list of numbers is the same before and after sorting. Since the same number of numbers is returned, the mean of the list of numbers is also the same before and after sorting.

What more could you ask for from a sorting algorithm?!