Counting Sort

Counting sort works by counting how many times each value appears, then using those counts to compute the exact final position of every value. It never compares two values against each other. Instead it uses each value as an index into a count array, builds prefix sums so each entry tells it where to place the next instance of that value, then writes every value directly into its sorted position.

Press play, or step through it one operation at a time. Orange highlights the value being read, yellow marks a position being written, and green means the final sorted result.

Try Sorted and Reversed. Both take exactly the same number of steps, because counting sort does not look at the overall order. It counts, builds prefix sums, and places, mechanically. The work is the same on any input of the same size and range.

Time and space complexity

Here k is the range: max - min + 1. For values between 10 and 82, k is 73. If all values fit in 0 to 99, k is at most 100, and the algorithm is effectively linear in n.

Step by step

1. Find the minimum and maximum values to determine the range k.
2. Create a count array of size k, initialised to zero.
3. Scan the input. For each value, increment its corresponding count.
4. Build prefix sums: each count[i] becomes the total of all counts up to and including index i. After this, count[v - min] tells you how many values are less than or equal to v.
5. Create an output array of size n.
6. Scan the input from right to left. For each value, read its prefix sum to find its final position, place it there, and decrement the count.
7. The output array is now sorted.

Scanning right to left in step 6 is what makes counting sort stable. Among equal values, the rightmost in the input gets the highest position in the output, so their relative order is preserved.

Worked example

Sorting [4, 2, 4, 1] (min = 1, max = 4, k = 4):

Result: [1, 2, 4, 4]. Four value inspections and four placements. The two 4s kept their original left-to-right order because we scanned right to left.

When to use it

The code

Every version below is the stable variant: it scans right to left in the placement phase, so equal values keep their original order.

def counting_sort(a):
    if not a:
        return a
    min_val = min(a)
    max_val = max(a)
    count = [0] * (max_val - min_val + 1)
    for val in a:
        count[val - min_val] += 1
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    output = [0] * len(a)
    for i in range(len(a) - 1, -1, -1):
        output[count[a[i] - min_val] - 1] = a[i]
        count[a[i] - min_val] -= 1
    return output


nums = [38, 27, 43, 10, 82, 15, 27, 61, 45, 38]
result = counting_sort(nums)
print(result)

Common questions