Counting Sort Animation
–
Waiting for input...
Initializing Count Array
Color: Active Element • Incrementing • Count Value
Counting Sort
Watch counting sort tally and place integers without comparisons.
Time O(n + k) · Space O(k)
Implementation
def counting_sort_stable_prefix_sums(arr):
ACCEPTABLE_RANGE_MAX = 30
if not arr or len(arr) <= 1:
return arr
smallest, biggest = min(arr), max(arr)
value_range = biggest - smallest + 1
if value_range > ACCEPTABLE_RANGE_MAX:
return None # range too large
offset = smallest # handles negative numbers
counter = [0] * value_range
for value in arr:
counter[value - offset] += 1
for i in range(1, len(counter)):
counter[i] += counter[i - 1]
result = [None] * len(arr)
for i in range(len(arr) - 1, -1, -1):
value = arr[i]
count_idx = value - offset
counter[count_idx] -= 1
result[counter[count_idx]] = value
return result
About Counting Sort
How Counting Sort Works
Counting sort is a non-comparison sorting algorithm that counts the occurrences of each value and uses arithmetic to determine positions. It runs in linear time when the range of values (k) is not significantly larger than the number of elements (n).
Count the occurrences of each distinct value in the input. Compute a prefix sum of the counts to determine output positions. Place each element in its correct position using the prefix sum, decrementing the count after each placement.
Complexity
- Time
- O(n + k)
- Space
- O(k)
When to Use Counting Sort
- Integer data with a known, bounded range
- When O(n) time is required and extra space is acceptable
- As a sub-routine in radix sort