Counting Sort, Bucket Sort and Radix Sort

Comparison sorts cannot beat O(n log n), but if the keys are small integers, or can be split into small digits, or are spread evenly over a known range, you can sort in linear time by using the values directly. In interviews these ideas show up less as "implement radix sort" and more as tricks inside other problems: bucket by frequency, count instead of sort, or use the pigeonhole principle to avoid sorting altogether.

Intuition

• Counting sort: if every key is an integer in [0, k), count how many times each key occurs. Prefix sums of the counts tell you where each key's block starts in the output, so every element can be written straight into its final slot. Cost O(n + k).
• Bucket sort: split the value range into buckets, drop each element into its bucket, sort each (small) bucket, and concatenate. With evenly spread data each bucket holds O(1) elements on average.
• Radix sort: sort by one digit at a time using a stable counting sort. LSD (least significant digit first) radix sort processes the last digit first; stability guarantees that ties on a higher digit stay ordered by the lower digits already processed.

When to use it in interviews / OAs

• Keys come from a small range: ages, scores 0 to 100, letters, the three colors of a "sort colors" question, counts bounded by n.
• Frequency questions: "k most frequent elements", "sort characters by frequency". Frequencies are integers between 1 and n, so bucket by frequency in O(n) instead of sorting or using a heap.
• "Linear time" or "O(n)" demanded for a sorting-flavored question, for example the maximum gap between neighbors in sorted order.
• Bounded answers: an h-index never exceeds n, so counts can be capped at n.
• Fixed-length strings or large integers: radix sort processes them digit by digit.

Template

Stable counting sort

def counting_sort(items: list, key, k: int) -> list:
    """Stable sort of items whose integer key(item) lies in [0, k). O(n + k)."""
    start = [0] * (k + 1)
    for it in items:
        start[key(it) + 1] += 1
    for v in range(k):  # prefix sums: start[v] = first output slot for key v
        start[v + 1] += start[v]
    out = [None] * len(items)
    for it in items:  # scanning left to right keeps equal keys in input order
        out[start[key(it)]] = it
        start[key(it)] += 1
    return out

If you only sort bare integers (no attached data), you can skip the placement step and rebuild the output from the counts: [v for v in range(k) for _ in range(count[v])].

Counting with a cap: h-index

The h-index is the largest h such that at least h papers have at least h citations. It can never exceed n, so any citation count above n can be treated as n, and counting replaces sorting:

def h_index(citations: list[int]) -> int:
    n = len(citations)
    count = [0] * (n + 1)
    for c in citations:
        count[min(c, n)] += 1  # cap at n
    papers = 0
    for h in range(n, -1, -1):
        papers += count[h]  # papers with at least h citations
        if papers >= h:
            return h
    return 0

Buckets indexed by frequency: top k frequent

from collections import Counter


def top_k_frequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]  # index = frequency
    for value, f in freq.items():
        buckets[f].append(value)
    result = []
    for f in range(len(nums), 0, -1):  # highest frequency first
        for value in buckets[f]:
            result.append(value)
            if len(result) == k:
                return result
    return result

Buckets plus pigeonhole: maximum gap in O(n)

Find the largest difference between consecutive elements of the sorted array without sorting. With n values between lo and hi, the largest gap is at least (hi - lo) / (n - 1). Use buckets narrower than that, so two values in the same bucket can never form the largest gap; the answer must be the distance from one non-empty bucket's maximum to the next non-empty bucket's minimum:

def maximum_gap(nums: list[int]) -> int:
    n = len(nums)
    if n < 2:
        return 0
    lo, hi = min(nums), max(nums)
    if lo == hi:
        return 0
    width = max(1, (hi - lo) // (n - 1))  # never larger than the answer
    count = (hi - lo) // width + 1
    mins: list = [None] * count
    maxs: list = [None] * count
    for x in nums:
        b = (x - lo) // width
        mins[b] = x if mins[b] is None else min(mins[b], x)
        maxs[b] = x if maxs[b] is None else max(maxs[b], x)
    best, prev_max = 0, lo
    for b in range(count):
        if mins[b] is not None:  # compare only across buckets
            best = max(best, mins[b] - prev_max)
            prev_max = maxs[b]
    return best

LSD radix sort for non-negative integers

def radix_sort(nums: list[int], base: int = 256) -> list[int]:
    out = list(nums)
    place = 1
    biggest = max(out, default=0)
    while place <= biggest:
        buckets: list[list[int]] = [[] for _ in range(base)]
        for x in out:  # stable: keeps the order produced by lower digits
            buckets[x // place % base].append(x)
        out = [x for bucket in buckets for x in bucket]
        place *= base
    return out

For negative numbers, sort the negatives and non-negatives separately (or add an offset so every key becomes non-negative).

Complexity

Algorithm	Time	Extra space	Stable
Counting sort, keys in [0, k)	O(n + k)	O(n + k)	Yes
Bucket sort, evenly spread data	O(n + number of buckets) on average, O(n^2) worst case	O(n + number of buckets)	Yes, with a stable inner sort
LSD radix sort, d digits in base b	O(d * (n + b))	O(n + b)	Yes
h_index, top_k_frequent, maximum_gap	O(n)	O(n)	n/a

Radix sort runs d = log_b(max value) + 1 passes; base 256 keeps the passes few while the count array stays tiny.

Common pitfalls

• Huge key range. Counting sort with keys up to 10^9 needs a 10^9-entry array. Compress the coordinates first, or fall back to a comparison sort.
• Negative keys. Shift by the minimum value before using keys as indices.
• Unstable inner sort in radix sort. Each pass must be stable or the earlier passes are destroyed.
• Skewed data in bucket sort. If everything lands in one bucket, you are back to the inner sort's worst case.
• Python reality check. The built-in sorted is implemented in C and is often faster than a hand-written linear sort for moderate n. Use these techniques when the problem demands O(n) or when counting is naturally simpler than sorting.
• Off-by-one in prefix sums. Decide whether start[v] means the first slot of key v (exclusive prefix sum, as above) or one past its last slot, and scan in the matching direction.

Interview variations

• Sort colors (only 0, 1 and 2): count and rewrite, or do a one-pass three-way partition.
• Relative sort array: count the values, then output them in the order given by a second array, followed by the rest in increasing order.
• Sort characters by frequency and top k frequent words: bucket by frequency (break ties alphabetically when asked).
• Maximum gap: buckets plus the pigeonhole principle, or radix sort, both O(n).
• Sorting fixed-length strings or IDs: LSD radix sort by character from right to left.
• Counting instead of sorting: anagram checks with a 26-entry count array, deciding whether two arrays are permutations of each other.