Counting Sort

Understand the idea

This version accepts non-negative integers and creates one count slot for every value through the maximum. Time and memory depend on both input length n and range k. A sparse list containing one extremely large identifier makes that allocation inappropriate. A frequency dictionary or comparison sort may be a better fit.

Where to try it

Open this example with Try in playground. The code loads as editable text and does not run until you select Run. The first run downloads Python. Each run starts fresh; temporary files created by a script are not files on your PC.

A worked example

def counting_sort(values):
    if not values:
        return []
    if min(values) < 0:
        raise ValueError("Non-negative integers required")
    counts = [0] * (max(values) + 1)
    for value in values:
        counts[value] += 1
    return [value for value, count in enumerate(counts) for _ in range(count)]

print(counting_sort([4, 1, 4, 0]))

Read the result

The output is [0, 1, 4, 4]. The count of 4 preserves its two occurrences.

Try one change

Test an empty input and explain why a billion-sized maximum would make this method unsuitable.