DSA Visual

Counting Sort

Watch counting sort tally and place integers without comparisons.

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

Approach

Stable Prefix Sums

Implementation

1def counting_sort_stable_prefix_sums(arr):
2    ACCEPTABLE_RANGE_MAX = 30
3
4    if not arr or len(arr) <= 1:
5        return arr
6
7    smallest, biggest = min(arr), max(arr)
8    value_range = biggest - smallest + 1
9    if value_range > ACCEPTABLE_RANGE_MAX:
10        return None  # range too large
11
12    offset = smallest  # handles negative numbers
13    counter = [0] * value_range
14    for value in arr:
15        counter[value - offset] += 1
16
17    for i in range(1, len(counter)):
18        counter[i] += counter[i - 1]
19
20    result = [None] * len(arr)
21    for i in range(len(arr) - 1, -1, -1):
22        value = arr[i]
23        count_idx = value - offset
24        counter[count_idx] -= 1
25        result[counter[count_idx]] = value
26
27    return result
28

Counting Sort Animation

Waiting for input...

No steps to display. Please provide input to visualize the algorithm.

-

More in Sorting

Bubble SortO(n²)Insertion SortO(n²)Selection SortO(n²)Merge SortO(n log n)Quick SortO(n log n)