Counting, radix and bucket sort | DSA

← BlogDATA STRUCTURES / ALGORITHMSPython example pack ↓

Comparison sorting must distinguish n! permutations, yielding a worst-case Ω(n log n) comparison lower bound. Counting sort changes the model by indexing bounded integers, so it does not violate that bound.

Counting uses frequencies and prefix positions; simply repeating values does not demonstrate stable record sorting. LSD radix processes low digits first and requires a stable digit sort, or earlier digit order is lost. Signed values, variable length and Unicode collation require explicit handling.

Bucket sort depends on distribution and may degrade when values collect in one bucket. A huge key range makes O(k) counting storage impractical even with small n; comparison sorting can then be preferable.

A worked trace

[2,0,2,1] gives count=[1,1,2] and [0,1,2,2]. k is range width, not distinct-value count.

Cost and assumptions

Counting O(n+k) time/space; radix with d digits and radix b is O(d(n+b)).

Executable example

Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.

Python 3

def counting_sort(a, k):
    counts = [0]*k
    for x in a:
        if not 0 <= x < k: raise ValueError("out of range")
        counts[x] += 1
    return [x for x, count in enumerate(counts) for _ in range(count)]
assert counting_sort([2,0,2,1], 3) == [0,1,2,2]

TEST YOUR UNDERSTANDING

Your turn

Why can selection sort be problematic as the digit sort in radix?

Reveal the reasoning

Standard selection sort is unstable and can destroy lower-digit order among equal current digits. Use a stable stage such as counting sort.

Take it further

Write down the input contract and the invariant before changing the example.
Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
Derive the cost under the stated model; measure several input sizes and explain discrepancies.

Primary reading & lecture notes

Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.

MIT 6.006 · Introduction to Algorithms ↗Princeton · Algorithms, Sedgewick & Wayne ↗

Solve the exercise before moving on.

RasimAtaberkŞahin