Counting idea

Count each value, use cumulative sums to sort.

Counting idea

Counting sort sorts without comparisons. It counts how many times each element appears, then builds the sorted output from these counts.

When keys are in a small integer range it runs in O(n + k); k is the key range. Faster than comparison sorts.

But if the range is large, k memory explodes. So it suits only small-range integer keys.

Range cost

Counting sort builds a count array from 0 to max(arr). The range is k = max - min + 1.

Memory is O(k). If k is very large (e.g. 0 to a million), storing this array is costly.

So counting sort is best on dense, narrow ranges. For negative numbers an offset is needed.

Exercise Count elements

Write count_value(arr, v). Count how many times v appears in arr. Print 3 with print(count_value([3, 1, 4, 1, 5, 1], 1)).

Show example solution

def count_value(arr, v):
    # Count v
    count = 0
    for x in arr:
        if x == v:
            count += 1
    return count
print(count_value([3, 1, 4, 1, 5, 1], 1))

Test yourself

When is counting sort efficient?
- Always
- On a small integer range
- Only on large arrays
- Only on text
Show answer

On a small integer range — On a small integer range

Range size

k = max(arr) - min(arr) + ____

Show answer

k = max(arr) - min(arr) + 1

Counting idea: match the terms

Counting sort

No comparison
Cost

O(n+k)
Memory

O(k)
Range

Must be narrow

Next lesson: Count array

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies