Skip to content
Laviyx Learn

Try

DSA course menu

Counting Sort and Radix Sort: Sorting in Linear Time

Learn non-comparison sorting: counting sort for small integer ranges, a stable counting sort, radix sort digit by digit, bucket sort, and when these beat O(n log n) sorts.

Intermediate8 min readUpdated
On this page

Any sort that works only by comparing pairs of items needs at least about n log n comparisons in the worst case; that is a proven limit. Counting sort and radix sort beat it by not comparing at all: they use the values themselves as positions.

The catch: they only work for keys with a limited range, like ages, exam marks or fixed-length numbers.

Counting sort#

Count how many times each value appears, then write the values out in order:

Python
def counting_sort(nums, max_value):
    counts = [0] * (max_value + 1)
    for x in nums:
        counts[x] += 1
    result = []
    for value, c in enumerate(counts):
        result.extend([value] * c)
    return result

marks = [7, 3, 9, 3, 10, 7, 7, 0, 5]
print(counting_sort(marks, 10))
Output
[0, 3, 3, 5, 7, 7, 7, 9, 10]

The time is O(n + k), where k is the range of values (here 0 to 10), and it needs O(k) extra memory. When k is small compared with n, that is linear time. When k is huge (sorting a few numbers up to a billion), it is hopeless.

Stable counting sort for records#

To sort records by a key, turn the counts into starting positions (a prefix sum), then place each record. Walking the input backwards keeps equal keys in their original order, which radix sort depends on:

Python
def counting_sort_by(records, key, max_key):
    counts = [0] * (max_key + 1)
    for r in records:
        counts[key(r)] += 1
    for k in range(1, max_key + 1):         # counts become end positions
        counts[k] += counts[k - 1]
    output = [None] * len(records)
    for r in reversed(records):             # backwards keeps it stable
        counts[key(r)] -= 1
        output[counts[key(r)]] = r
    return output

students = [("Asha", 2), ("Ravi", 1), ("Meera", 2), ("John", 0), ("Priya", 1)]
print(counting_sort_by(students, key=lambda s: s[1], max_key=2))
Output
[('John', 0), ('Ravi', 1), ('Priya', 1), ('Asha', 2), ('Meera', 2)]

Ravi is still before Priya, and Asha before Meera: stable.

Radix sort#

Radix sort sorts numbers one digit at a time, from the least significant (ones) to the most significant, using a stable counting sort for each digit. Because each pass is stable, the order from earlier digits is kept as later digits are sorted.

Python
def radix_sort(nums):
    if not nums:
        return nums
    place = 1
    while max(nums) // place > 0:
        nums = counting_sort_by(nums, key=lambda x: (x // place) % 10, max_key=9)
        print(f"after the {place}s digit: {nums}")
        place *= 10
    return nums

def counting_sort_by(records, key, max_key):
    counts = [0] * (max_key + 1)
    for r in records:
        counts[key(r)] += 1
    for k in range(1, max_key + 1):
        counts[k] += counts[k - 1]
    output = [None] * len(records)
    for r in reversed(records):
        counts[key(r)] -= 1
        output[counts[key(r)]] = r
    return output

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
Output
after the 1s digit: [170, 90, 802, 2, 24, 45, 75, 66]
after the 10s digit: [802, 2, 24, 45, 66, 170, 75, 90]
after the 100s digit: [2, 24, 45, 66, 75, 90, 170, 802]
[2, 24, 45, 66, 75, 90, 170, 802]

With d digits per number, radix sort is O(d · (n + 10)). For numbers with a fixed number of digits, that is O(n).

Bucket sort#

Bucket sort spreads values that are roughly uniform over a range into buckets, sorts each small bucket, and joins them. For decimals between 0 and 1:

Python
def bucket_sort(values, buckets=5):
    groups = [[] for _ in range(buckets)]
    for v in values:
        groups[min(int(v * buckets), buckets - 1)].append(v)
    result = []
    for g in groups:
        result.extend(sorted(g))     # each bucket is small
    return result

print(bucket_sort([0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]))
Output
[0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]

With evenly spread data, each bucket holds a few items and the total is about O(n). If everything lands in one bucket, it degrades to the cost of the inner sort.

Which sort when?#

SituationGood choice
general data in Pythonsorted() / list.sort() (Timsort, O(n log n), stable)
small integer range (marks, ages)counting sort, O(n + k)
fixed-length integers or stringsradix sort
uniformly spread decimalsbucket sort
need the kth item, not a full sortquickselect or a heap

Common mistakes#

Practice#

Practice exercise

Write h_index(citations): the largest h such that the researcher has at least h papers with at least h citations each. Use counting (O(n)), not sorting. For [3, 0, 6, 1, 5] the answer is 3.

Show hint

No h can exceed n (the number of papers), so count citations, putting anything above n into bucket n. Then walk from n down to 0, keeping a running total of papers with at least that many citations; the first time the total reaches the current value, that value is h.

Show solution
Python
def h_index(citations):
    n = len(citations)
    counts = [0] * (n + 1)
    for c in citations:
        counts[min(c, n)] += 1
    papers = 0
    for h in range(n, -1, -1):
        papers += counts[h]
        if papers >= h:
            return h
    return 0

print(h_index([3, 0, 6, 1, 5]))
print(h_index([1, 3, 1]))
print(h_index([0, 0]))
Output
3
1
0

Key takeaway#

Next: hierarchical data, in Trees and Binary Trees.

Finished this lesson?

Related lessons

DSAMerge Sort in Python: Divide and Conquer ExplainedLearn merge sort: splitting a list in half, sorting each half recursively, merging two sorted lists, why it is O(n log n), its O(n) memory cost, and counting inversions with merge sort.Intermediate10 min readDSAQuick Sort in Python: Partitioning, Pivots and QuickselectLearn quick sort: choosing a pivot, the Lomuto partition scheme, in-place recursive sorting, why it is O(n log n) on average but O(n²) in the worst case, random pivots, and quickselect for the kth smallest item.Intermediate11 min readDSAHash Tables Explained: How Dictionaries and Sets WorkLearn how hash tables work: hash functions, buckets, collisions, chaining, load factor and resizing, why dict and set lookups are O(1) on average, and classic hashing problems like two sum.Beginner9 min read