Editor

Counting sort in Python

Counting sort never compares two values: it counts how many times each value appears, then writes the values back in order. It works when the values are small whole numbers.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. Make counts, a list of zeros with one slot for every value from 0 to max(nums).
  2. Walk through nums once and add 1 to counts[value] for each value.
  3. Walk through counts in order: each value is written into nums as many times as it was counted.
  4. i is the next position to fill, so the list is rewritten from left to right in sorted order.
  5. Here k is the largest value: the time is O(n + k), so counting sort suits small ranges like marks or ages.

What to watch

  • Watch counts fill up during the first loop while the bars stay still.
  • Watch the second loop overwrite the bars from the left, smallest values first.
  • Watch values 2 and 4: their count is 0, so the inner loop writes nothing for them.

The code

def counting_sort(nums):
    counts = [0] * (max(nums) + 1)   # one counter per value, 0 to max
    for value in nums:
        counts[value] += 1
    i = 0                            # next position to fill in nums
    for value, count in enumerate(counts):
        for _ in range(count):
            nums[i] = value
            i += 1
    return nums

data = [5, 1, 3, 5, 0, 1, 3]
print(counting_sort(data))
Output
[0, 1, 1, 3, 3, 5, 5]

Open it in the editor · Python Program for Counting Sort, explained