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.
| Property | Value |
|---|---|
| Time | O(n + k), where k is the size of the key range |
| Extra space | O(n + k) |
| Stable | yes, in the prefix-sum version |
| Requirement | integer keys from a small range |
Counting sort example
The following is the simplest form of counting sort for non-negative integers.
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.
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.
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.
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.
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.
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.
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.
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.
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
List all Python tutorials.