Counting Sort in Data Structure

Counting Sort is a non-comparison-based sorting algorithm that counts the number of occurrences of each distinct value in the input, then uses those counts to place elements directly into their sorted position.

Algorithm Steps

• Find the range of input values (minimum and maximum).
• Create a count array to store the frequency of each value.
• Transform the count array so each element holds the cumulative count (sum of previous counts).
• Place each input element into the output array based on its cumulative count, then decrement the count.

def counting_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    output = [0] * len(arr)
    for num in reversed(arr):
        count[num] -= 1
        output[count[num]] = num
    return output

Complexity

Here n is the number of elements and k is the range of input values. Counting Sort is efficient only when k is not significantly larger than n.

Applications

• Sorting grades, ages, or other bounded-range integer data.
• Used as a subroutine within Radix Sort.
• Frequency-based data analysis.