Sorting

Counting Sort

TimeO(n + k) SpaceO(n + k)

Imagine sorting exam papers by grade (A through F). You make 5 piles labeled A-F, drop each paper in its pile, then stack the piles in order. You never compared two papers — you just classified each one. That’s counting sort.

When to use it: The values are integers (or can be mapped to integers) within a known, small range k. When k is O(n), this sorts in linear time, beating the O(n log n) comparison-sort lower bound.

Key insight: By counting how many times each value appears, you can directly compute where each element belongs in the output — no comparisons needed.

Common trap: Using counting sort when the range k is much larger than n (e.g., sorting 100 numbers in range 0 to 10 million). The O(k) space and time make it impractical.

function countingSort(arr, maxVal):
    # Step 1: Count occurrences
    count = array of size (maxVal + 1), initialized to 0
    for num in arr:
        count[num] = count[num] + 1

    # Step 2: Compute cumulative counts (prefix sum)
    # count[i] now tells us the end position for value i
    for i = 1 to maxVal:
        count[i] = count[i] + count[i - 1]

    # Step 3: Build output array (iterate backwards for stability)
    output = array of size length(arr)
    for i = length(arr) - 1 down to 0:
        value = arr[i]
        count[value] = count[value] - 1
        output[count[value]] = value

    return output

def counting_sort(arr: list[int]) -> list[int]:
    """Stable counting sort for non-negative integers."""
    if not arr:
        return []

    max_val = max(arr)
    count = [0] * (max_val + 1)

    # Count occurrences
    for num in arr:
        count[num] += 1

    # Cumulative count
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # Build output (backwards for stability)
    output = [0] * len(arr)
    for num in reversed(arr):
        count[num] -= 1
        output[count[num]] = num

    return output


def counting_sort_with_negatives(arr: list[int]) -> list[int]:
    """Handle arrays that may contain negative integers."""
    if not arr:
        return []

    min_val = min(arr)
    max_val = max(arr)
    range_size = max_val - min_val + 1

    count = [0] * range_size
    for num in arr:
        count[num - min_val] += 1

    for i in range(1, range_size):
        count[i] += count[i - 1]

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

    return output

Problem: Sort an array of n integers where all values are between 0 and 100.

How would you approach this?

Answer: This is counting sort because the value range (k = 100) is small and fixed. Count occurrences of each value, compute prefix sums, and place elements directly. Time: O(n + 100) = O(n).

Problem: Given an array of strings, sort them by their length (lengths range from 1 to 1000).

How would you approach this?

Answer: This is counting sort using string length as the key. Since lengths are bounded integers in a small range, counting sort gives O(n + k) time where k = 1000. The stable version preserves alphabetical order among same-length strings.

Time: O(n + k) where n is the number of elements and k is the range of values. We make one pass to count (O(n)), one pass to compute prefix sums (O(k)), and one pass to place elements (O(n)).

Space: O(n + k) for the count array of size k and the output array of size n. This is the trade-off for linear time — counting sort uses more space than comparison sorts.