# 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*.

**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

## Implementation

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 4 March 2019.

HTML page formatted Wed Mar 13 12:42:45 2019.

Cite this as:

Art S. Kagel, "counting sort", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 4 March 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/countingsort.html