DSA Counting Sort

Why Counting Sort Is Different

Every algorithm covered so far — insertion sort, quick sort, and merge sort — decides ordering by comparing pairs of elements. Counting sort takes a different approach: it counts how many times each distinct value appears in the input, then uses those counts to compute exactly where each value belongs in the sorted output. Because it never compares two elements directly, it can beat the O(n log n) lower bound that applies to comparison-based sorts.

• Find the range of values in the input, from the minimum to the maximum.
• Create a counts array with one slot per possible value, initialized to zero.
• Scan the input once, incrementing the count for each value seen.
• Convert counts into cumulative counts to know each value's final position.
• Build the sorted output by placing each input element at its computed position.

def counting_sort(arr):
    if not arr:
        return arr
    maximum = max(arr)
    counts = [0] * (maximum + 1)
    for num in arr:
        counts[num] += 1
    result = []
    for value, count in enumerate(counts):
        result.extend([value] * count)
    return result

print(counting_sort([4, 2, 2, 8, 3, 3, 1]))

When Counting Sort Applies

Counting sort only works well when the values being sorted are integers (or can be mapped to small integers) drawn from a range that is not much larger than the number of elements. It is commonly used for sorting exam scores, ages, small categorical codes, or as a stable subroutine inside radix sort for sorting larger numbers digit by digit.

def counting_sort_stable(arr, key=lambda x: x):
    if not arr:
        return arr
    max_key = max(key(x) for x in arr)
    counts = [0] * (max_key + 1)
    for item in arr:
        counts[key(item)] += 1
    for i in range(1, len(counts)):
        counts[i] += counts[i - 1]
    output = [None] * len(arr)
    for item in reversed(arr):
        k = key(item)
        counts[k] -= 1
        output[counts[k]] = item
    return output

records = [('apple', 3), ('banana', 1), ('cherry', 3), ('date', 1)]
print(counting_sort_stable(records, key=lambda r: r[1]))

Complexity Analysis

def sort_string_chars(text):
    counts = [0] * 26
    for ch in text:
        counts[ord(ch) - ord('a')] += 1
    result = []
    for i, count in enumerate(counts):
        result.append(chr(i + ord('a')) * count)
    return ''.join(result)

print(sort_string_chars('banana'))