DSA Counting Sort

How it works

This value-only implementation offsets negative keys by the smallest value and rejects a range larger than its configured slot budget. A small input with two extremely distant keys can still demand an unreasonable counting array without that check. Reconstructing repeated integers does not preserve separate record identities; stable record-based counting sort would need a different placement stage. The function deliberately rejects non-integer keys rather than silently coercing them.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as counting-sort.py and run python counting-sort.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def counting_sort(values, max_span=10000):
    if any(type(value) is not int for value in values):
        raise ValueError("Integer keys required")
    if not values:
        return []
    low, high = min(values), max(values)
    span = high - low + 1
    if span > max_span:
        raise ValueError("Key range exceeds the chosen budget")
    counts = [0] * span
    for value in values:
        counts[value - low] += 1
    result = []
    for offset, count in enumerate(counts):
        result.extend([low + offset] * count)
    return result

print(counting_sort([4, -2, 4, 0, -2]))
try:
    counting_sort([0, 1000000])
except ValueError as error:
    print(error)

Expected result

[-2, -2, 0, 4, 4]
Key range exceeds the chosen budget

The negative offset makes a small signed range practical, while the wide-range fixture fails before allocating its counting table. The slot budget is a teaching resource policy, not a claim that every environment can afford that many Python objects.

Time, space and assumptions

For n integers and range size k, this implementation takes O(n+k) time and O(n+k) output/workspace. The configured bound is checked before the O(k) count allocation.