Output array

Use the count array to produce a stable output.

Output array

The output array is built from the cumulative count. Each element is placed at the position the cumulative count points to; this finds the correct sorted position.

For stability we walk the array back to front: output[count[arr[i]] - 1] = arr[i], then count[arr[i]] -= 1. This preserves the order of equal-key elements.

Going backwards preserves the relative order of equal elements. This makes counting sort stable and the foundation of radix sort.

Stability

By placing back to front, counting sort is stable. The first equal element stays first in the sorted array; this order is preserved without change.

This matters when sorting records with satellite data: records with equal keys keep their original order and secondary information is not lost.

Radix sort's stability relies on this counting sort stability; that is why radix sort uses counting sort for each digit pass.

Exercise Counting sort

Write counting_sort(arr). Count array + cumulative + place backward. Print [1, 2, 2, 3, 3, 4, 8] with print(counting_sort([4, 2, 2, 8, 3, 3, 1])).

Show example solution

def counting_sort(arr):
    # Counting sort
    if not arr:
        return []
    k = max(arr) + 1
    count = [0] * k
    for x in arr:
        count[x] += 1
    for i in range(1, k):
        count[i] += count[i - 1]
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
    return output
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))

Test yourself

Output array: match the terms

Output

output
Cumulative

Position
Walk backward

Stable
count -= 1

Free slot
Why is counting sort stable?
- Random order
- No comparison
- Only on small arrays
- It places back to front
Show answer

It places back to front — It places back to front

Placement

output[count[arr[i]] - ____] = arr[i]

Show answer

output[count[arr[i]] - 1] = arr[i]

Next lesson: Summary - Counting sort

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies