# 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_{2} *N*) rods, where *N* is the maximum
of the numbers to be sorted. The least significant rod represents 2^{0} 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?!

Home | Esoteric Programming Languages

*Last updated: Saturday, 21 March, 2009; 17:12:45 PDT.*

Copyright © 1990-2016, David Morgan-Mar. *dmm@dangermouse.net*

*Hosted by: DreamHost*