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 ...)
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.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 27 November 2019.
HTML page formatted Wed Nov 27 08:41:29 2019.
Cite this as:
Art S. Kagel, "counting sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 27 November 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/countingsort.html