countingsort

Counting sort is a non-comparative sorting algorithm designed for integers that fall within a known, bounded range. The core idea is to count how many times each value appears and then use those counts to place elements directly into the correct positions in the output array. A counts array is created with a size equal to the range of input values. Each element in the input increments the count at its value index. If the data range does not start at zero, the values can be shifted by subtracting the minimum value to fit into an indexable range.

To produce a sorted sequence, a second pass converts the frequency counts into starting indices. This is commonly done by computing a running total (prefix sum) of the counts. Then, by traversing the input from the end to the beginning (for stability) we place each element into the output array at its corresponding index and decrement the running total for that value.

Counting sort runs in linear time relative to n and the range: time complexity is O(n + k), where n is the number of elements and k is the size of the range. The memory usage is O(k). It is stable if the placement step processes elements from right to left. Because it relies on a direct index into the counts array, it is not suitable for large ranges with sparse data. It is typically used for sorting integers or keys that can be mapped to a small range and is also used as a preprocessing step in radix sort.