counting sort

(algorithm)

Definition: A 2-pass sort algorithm that is efficient when the number of distinct keys is small compared to the number of items. The first pass counts the occurrences of each key in an auxiliary array, and then makes a running total so each auxiliary entry is the number of preceding keys. The second pass puts each item in its final place according to the auxiliary entry for that key.

Generalization (I am a kind of ...)
histogram sort.

Note: A bucket sort uses fixed-size buckets. A histogram sort sets up buckets of exactly the right size in a first pass. A counting sort is a histogram sort with one bucket per possible key value. A pigeonhole sort is a counting sort that moves items to the auxiliary array instead of counting them.

Author: ASK

Implementation

Marion McCoskey's Single Buffered Count Sort (C++). Bruno R. Preiss' sort integers 0 to m-1 (C).

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 28 November 2014.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Art S. Kagel, "counting sort", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 28 November 2014. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/countingsort.html