Tally sort
From Wikipedia, the free encyclopedia
The tally sort (also called set sort or bit sort) algorithm is specialized variant of a pigeonhole sort (with some characteristics of a counting sort). It uses a bit array to represent the range of values, with one bit for each possible value in the range. As each element is tested, the corresponding bit is set. This is not a true sorting algorithm, as the original data is discarded, but can be used to avoid sorting under certain circumstances. It operates in linear time and fixed space, and is an online algorithm.
[edit] Reference
- chapter 1 of Jon Bentley's Programming Pearls ISBN 0-201-10331-1
