Counting sort (small range)

Challenge

Sort an array of small non-negative integers using counting sort.

Task

Implement void counting_sort(int *a, size_t n, int max_val) that sorts the n elements of a into non-decreasing order, in place. Every value is in the range [0, max_val].

Input

• a: writable array of n ints, each in [0, max_val].
• n: the number of elements.
• max_val: the largest possible value (max_val <= 1000).

Output

Nothing returned; a[0..n-1] is sorted in place.

Example

{3,1,4,1,5,9,2,6,5,3,5}, max_val=9   ->   {1,1,2,3,3,4,5,5,5,6,9}
{0,0,0,1,1,1}, max_val=1              ->   {0,0,0,1,1,1}

Edge cases

• n == 0 returns immediately.
• All-equal input and already-sorted input both work.

Rules

• Use a histogram of counts, not comparisons. O(n + max_val) time; you may allocate O(max_val) memory (and must free it).

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: n ints each in [0, max_val]; n; max_val (<= 1000).

Output format

Nothing returned; a is sorted non-decreasing in place.

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.