(algorithm)
Definition: A 2-pass sort algorithm that is efficient when the range of keys is small and there many duplicate keys. 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.
See also American flag sort, bingo sort, pigeonhole 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
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 2 June 2006.
HTML page formatted Mon Sep 11 09:46:02 2006.
Cite this as:
Art S. Kagel, "counting sort", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 2 June 2006. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/countingsort.html
