(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.
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 Black.
Entry modified 21 April 2022.
HTML page formatted Thu Apr 21 14:52:02 2022.
Cite this as:
Art S. Kagel, "counting sort", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 21 April 2022. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/countingsort.html