ZetCode

Python counting sort

last modified November 18, 2026 Python 3.15

In this article we explain the counting sort algorithm in Python. We implement the simple and the stable version, sort negative numbers, records, and letters, and show when counting sort beats the built-in sorted function and when it fails.

Most sorting algorithms compare elements with each other. It can be proved that a comparison sort needs Ω(n log n) comparisons in the worst case. Counting sort does not compare elements at all. It works with small non-negative integer keys and uses them directly as list indexes, which allows it to sort in linear time.

Counting sort algorithm

Counting sort creates a list of counters, one for each possible key value. It goes through the input once and counts how many times each value occurs. Then it goes through the counters in order and outputs each value as many times as it was counted.

PropertyValue
TimeO(n + k), where k is the size of the key range
Extra spaceO(n + k)
Stableyes, in the prefix-sum version
Requirementinteger keys from a small range

Counting sort example

The following is the simplest form of counting sort for non-negative integers.

counting_sort.py
def counting_sort(vals):
    if not vals:
        return []
    counts = [0] * (max(vals) + 1)
    for v in vals:
        counts[v] += 1
    res = []
    for v, count in enumerate(counts):
        res.extend([v] * count)
    return res


nums = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(nums))

The counts list has one counter for every value from 0 to the maximum. The first loop increments the counter of each value. The second loop uses enumerate to get each value with its count and appends the value count times. The empty list is handled separately, because max raises a ValueError on an empty sequence.

$ python counting_sort.py
[1, 2, 2, 3, 3, 4, 8]

Tracing the counts

We print the counters next to the values they belong to.

counting_trace.py
nums = [4, 2, 2, 8, 3, 3, 1, 0, 4]

counts = [0] * (max(nums) + 1)
for v in nums:
    counts[v] += 1

print('value: ', list(range(len(counts))))
print('counts:', counts)

res = []
for v, count in enumerate(counts):
    res.extend([v] * count)
print('sorted:', res)

The index of a counter is the value it counts. Values 5, 6, and 7 do not occur in the input, so their counters stay at zero and they do not appear in the output.

$ python counting_trace.py
value:  [0, 1, 2, 3, 4, 5, 6, 7, 8]
counts: [1, 1, 2, 2, 2, 0, 0, 0, 1]
sorted: [0, 1, 2, 2, 3, 3, 4, 4, 8]

Negative numbers

List indexes cannot be negative. We shift the values by the minimum, so the smallest value maps to index 0.

negative.py
def counting_sort(vals):
    if not vals:
        return []
    lo, hi = min(vals), max(vals)
    counts = [0] * (hi - lo + 1)
    for v in vals:
        counts[v - lo] += 1
    res = []
    for offset, count in enumerate(counts):
        res.extend([offset + lo] * count)
    return res


temps = [3, -7, 0, 12, -2, 5, -7, 8, 3, -1]
print(counting_sort(temps))
print(counting_sort([1003, 1001, 1002, 1001]))

The counter list has hi - lo + 1 elements. A value v is counted at index v - lo and restored by adding lo back. The offset also saves memory for values that do not start at zero; the numbers 1001 to 1003 need only three counters.

$ python negative.py
[-7, -7, -2, -1, 0, 3, 3, 5, 8, 12]
[1001, 1001, 1002, 1003]

Stable counting sort

The simple version rebuilds values from counts, so it can sort only plain numbers. To sort records by an integer key, we compute the starting position of each key in the output from the counts, and then place the records there.

stable_counting.py
def counting_sort(items, key, max_key):
    counts = [0] * (max_key + 1)
    for item in items:
        counts[key(item)] += 1

    starts = [0] * (max_key + 1)
    for k in range(1, max_key + 1):
        starts[k] = starts[k - 1] + counts[k - 1]
    print('counts:', counts)
    print('starts:', starts)

    res = [None] * len(items)
    for item in items:
        k = key(item)
        res[starts[k]] = item
        starts[k] += 1
    return res


students = [('Paul', 3), ('Anna', 1), ('Lucy', 2), ('Peter', 3),
            ('Robert', 1), ('Jane', 2), ('Mark', 5), ('Eva', 1)]

for name, grade in counting_sort(students, key=lambda s: s[1], max_key=5):
    print(grade, name)

The starts list holds the prefix sums of the counts: the records with key k start after all records with smaller keys. The last loop goes through the input in its original order and puts each record at the next free position of its key. Records with the same key therefore keep their input order, so the sort is stable. Stability is essential when counting sort is used as a step of radix sort.

$ python stable_counting.py
counts: [0, 3, 2, 2, 0, 1]
starts: [0, 0, 3, 5, 7, 7]
1 Anna
1 Robert
1 Eva
2 Lucy
2 Jane
3 Paul
3 Peter
5 Mark

Counting with collections.Counter

When the keys are not small integers, we can count them with a dictionary. The collections.Counter class does exactly that.

counter_sort.py
from collections import Counter

words = ['red', 'blue', 'red', 'green', 'blue', 'red', 'amber', 'green']
counts = Counter(words)
print(counts)

res = [w for w in sorted(counts) for _ in range(counts[w])]
print(res)

The counter maps each distinct word to its count. We sort only the distinct keys and repeat each one by its count. This is fast when there are many duplicates: sorting k distinct keys costs O(k log k), plus O(n) for counting and output.

$ python counter_sort.py
Counter({'red': 3, 'blue': 2, 'green': 2, 'amber': 1})
['amber', 'blue', 'blue', 'green', 'green', 'red', 'red', 'red']

Sorting letters

Lowercase ASCII letters are a small, fixed range of 26 keys, a perfect fit for counting sort.

letters.py
def sort_letters(text):
    counts = [0] * 26
    for ch in text:
        counts[ord(ch) - ord('a')] += 1
    return ''.join(chr(ord('a') + i) * c for i, c in enumerate(counts))


def anagram_key(word):
    counts = [0] * 26
    for ch in word:
        counts[ord(ch) - ord('a')] += 1
    return tuple(counts)


print(sort_letters('counting'))
print(sort_letters('mississippi'))

words = ['listen', 'silent', 'enlist', 'google', 'inlets', 'banana']
groups = {}
for word in words:
    groups.setdefault(anagram_key(word), []).append(word)
print([g for g in groups.values() if len(g) > 1])

The ord function converts a letter to its code; subtracting the code of a gives an index from 0 to 25. Two words are anagrams if they have the same letter counts, so the tuple of counts serves as a dictionary key that groups anagrams in O(n) time per word, without sorting the letters.

$ python letters.py
cginnotu
iiiimppssss
[['listen', 'silent', 'enlist', 'inlets']]

Descending order

For a descending order, we read the counters from the end.

descending.py
def counting_sort(vals, reverse=False):
    if not vals:
        return []
    lo, hi = min(vals), max(vals)
    counts = [0] * (hi - lo + 1)
    for v in vals:
        counts[v - lo] += 1
    order = range(hi - lo, -1, -1) if reverse else range(hi - lo + 1)
    return [lo + k for k in order for _ in range(counts[k])]


ratings = [4, 5, 3, 5, 1, 4, 4, 2, 5]
print(counting_sort(ratings))
print(counting_sort(ratings, reverse=True))

The order range runs backwards when reverse is true. The list comprehension expands each value by its count.

$ python descending.py
[1, 2, 3, 4, 4, 4, 5, 5, 5]
[5, 5, 5, 4, 4, 4, 3, 2, 1]

The range problem

Counting sort needs one counter for every value between the minimum and the maximum, whether the value occurs or not.

range_problem.py
import sys

vals = [3, 1_000_000_000, 7]
size = max(vals) - min(vals) + 1
print(f'{len(vals)} values need {size:,} counters')

counts = [0] * 1_000_000
print(f'1,000,000 counters take {sys.getsizeof(counts):,} bytes')

Three numbers would need almost a billion counters. A Python list stores an 8-byte pointer per element, so a million counters already take 8 MB, and a billion would take 8 GB. Counting sort is only practical when the range k is not much larger than the number of elements n. For large keys, radix sort applies counting sort to one digit at a time.

$ python range_problem.py
3 values need 999,999,998 counters
1,000,000 counters take 8,000,056 bytes

Benchmark

We compare counting sort, the Counter version, and sorted on a million integers from a small and from a large range.

benchmark.py
import random
import timeit
from collections import Counter


def counting_sort(vals):
    lo, hi = min(vals), max(vals)
    counts = [0] * (hi - lo + 1)
    for v in vals:
        counts[v - lo] += 1
    res = []
    for offset, count in enumerate(counts):
        res.extend([offset + lo] * count)
    return res


def counter_sort(vals):
    counts = Counter(vals)
    res = []
    for v in sorted(counts):
        res.extend([v] * counts[v])
    return res


rng = random.Random(14)

for k in (100, 1_000_000):
    data = [rng.randrange(k) for _ in range(1_000_000)]
    print(f'1,000,000 values in range({k:,})')
    for func in (counting_sort, counter_sort, sorted):
        t = timeit.timeit(lambda: func(data), number=3) / 3
        print(f'  {func.__name__:<14} {t:.4f} s')

With only 100 distinct values, both counting versions beat sorted, even though they are written in Python. The Counter version is the fastest, because the counting loop runs in C. With a million possible values, there are few duplicates and Counter has to sort almost all keys, so it falls behind. The times vary between runs and machines.

$ python benchmark.py
1,000,000 values in range(100)
  counting_sort  0.0478 s
  counter_sort   0.0275 s
  sorted         0.0842 s
1,000,000 values in range(1,000,000)
  counting_sort  0.2061 s
  counter_sort   0.5074 s
  sorted         0.2366 s

Source

collections.Counter – Python documentation

Sorting Techniques – Python documentation

In this article we have implemented counting sort in Python and examined its strengths and limits. See also Python radix sort, Python bucket sort, Python quick sort, and Python collections.

Author

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all Python tutorials.