counting sort

A non-comparison sort for small non-negative integers that counts how many times each value occurs and then writes the values back out in order.

In more detail

It runs in O(n + k) time, where k is the range of possible key values, and needs O(k) extra memory for the count array. When k is small it beats any comparison sort. When k is huge, such as general Unicode strings or 64-bit integers, the count array becomes impossibly large.

Related terms

Taught in

References