Counting sort

Problem¶

Implement stable counting sort for integers, including negative integers.

Key trick¶

Translate each value by the minimum, convert counts into ending positions, and place input values from right to left.

The right-to-left placement makes the standard record-based version stable.

For linked lists, counting values and rebuilding nodes is possible, but this is usually less natural than merge sort.

Trap¶

Its complexity depends on \(k = \max(nums)-\min(nums)+1\); a huge range makes it impractical.

Why is it interesting?¶

It beats the comparison-sorting lower bound by exploiting bounded integer keys.

Python solution¶

class sort_counting_sort:
    def sort(self, nums: list[int]) -> list[int]:
        if not nums:
            return []

        lo = min(nums)
        hi = max(nums)

        # Offsetting by `lo` supports negative integers.
        counts = [0] * (hi - lo + 1)

        # Count occurrences of each value.
        for x in nums:
            counts[x - lo] += 1

        # Convert frequencies into cumulative ending positions.
        for i in range(1, len(counts)):
            counts[i] += counts[i - 1]

        res = [0] * len(nums)

        # Traverse right-to-left so equal records retain their relative order.
        for x in reversed(nums):
            idx = x - lo

            # Decrement first to obtain the zero-based output position.
            counts[idx] -= 1
            res[counts[idx]] = x

        return res