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
- radix sort — A non-comparison sort that sorts integers one digit at a time, using a stable sort such as counting sort for each digit.
- comparison sort lower bound — The proven fact that any sort that only compares pairs must make at least about n log n comparisons in the worst case.
- auxiliary space — The memory an algorithm allocates beyond the input itself, such as a temporary copy or a helper array.
Taught in
- Counting And Radix Sort: Beating N Log N — Algorithms & Data Structures for Working Engineers