Counting sort (small range)

Challenge

Implement void counting_sort(int *a, size_t n, int max_val). All values are in [0, max_val]. Sort in place.

Why this matters

When values are small integers, counting sort beats comparison sorts by skipping comparisons entirely — O(n + k) time. It's the backbone of radix sort and many histogramming pipelines.

Input format

a[i] in [0, max_val] for all i. max_val <= 1000.

Output format

a sorted non-decreasing.

Constraints

O(n + max_val) time; you may allocate O(max_val) memory.

Starter code

#include <stddef.h>
void counting_sort(int *a, size_t n, int max_val) { /* TODO */ }

Common mistakes

Forgetting to free the count array; using int for sizes that need size_t; writing back in reverse order.

Edge cases to handle

n==0 returns immediately. All-equal input. Input already sorted.

Complexity

Time O(n + k). Space O(k) where k = max_val + 1.