Counting Sort and Radix Sort in Python: When O(n) Sorting Is Legit

A product page has to show customer reviews ordered by star rating, and ratings are always whole numbers from 1 to 5. Do you need to compare reviews with one another at all? You do not. Five buckets would be enough: drop each review into the bucket for its rating and read the buckets out in order. That is a sort that never asks "is this review greater than that one?", and it runs in time proportional to the number of reviews. It looks like it breaks the speed limit of sorting, and it does not, because the speed limit never applied to it.

Where the n log n limit comes from

Any algorithm that learns about the order of items only by comparing pairs must be able to distinguish all n! possible orderings of its input. Each comparison has two outcomes, so telling n! orderings apart needs at least log2(n!) comparisons, which grows like n log n. That bound is a proof about comparison sorts. Merge sort and quicksort live under it. An algorithm that uses the keys themselves as positions or buckets does not compare, so it is not bound by it, at the price of strong assumptions about the keys.

Counting sort for a small key range

Count how many reviews carry each rating. A running total of those counts says where each rating's block starts in the output. Then place each review at its rating's next free position. Going through the input left to right keeps reviews with equal ratings in their original order, so the sort is stable and the review text travels with the rating.

def counting_sort_by_rating(reviews, max_rating=5):
    """reviews: list of (reviewer, rating) with rating in 1..max_rating.
    Returns a new list ordered by rating, equal ratings keeping their original order."""
    counts = [0] * (max_rating + 1)
    for _, rating in reviews:
        counts[rating] += 1
    # turn counts into starting positions
    start, total = [0] * (max_rating + 1), 0
    for rating in range(1, max_rating + 1):
        start[rating] = total
        total += counts[rating]
    out = [None] * len(reviews)
    for review in reviews:                    # left to right keeps it stable
        rating = review[1]
        out[start[rating]] = review
        start[rating] += 1
    return out


reviews = [("Asha", 4), ("Bo", 2), ("Cyrus", 5), ("Dana", 4), ("Eli", 1), ("Fumi", 2), ("Gus", 4)]
for name, rating in counting_sort_by_rating(reviews):
    print(rating, name)

1 Eli
2 Bo
2 Fumi
4 Asha
4 Dana
4 Gus
5 Cyrus

The work is one pass to count, one pass over the k possible keys, and one pass to place: O(n + k) time and O(n + k) space. With n reviews and k = 5 that is essentially linear. Read what happened to ties: Bo before Fumi, and Asha, Dana, Gus in their input order. That detail is what makes counting sort usable as a building block, as the next section shows.

Radix sort: one stable pass per digit

What if the keys range over a million values, such as six-digit routing codes? A counting array of a million slots per sort is wasteful, but you can sort digit by digit instead. LSD (least significant digit) radix sort sorts the whole list by the last digit, then by the second last, and so on up to the first. Each pass is a stable counting sort over only ten possible digits. Stability is the whole mechanism: when the later pass sorts by a more significant digit, ties keep the order that earlier passes created, so the final list is ordered by the entire code.

def counting_pass(codes, digit_pos):
    """Stable counting sort of equal-length digit strings by one digit (0 = rightmost)."""
    buckets = [[] for _ in range(10)]
    for code in codes:
        buckets[int(code[-1 - digit_pos])].append(code)
    return [code for bucket in buckets for code in bucket]


def radix_sort_codes(codes):
    """LSD radix sort: one stable pass per digit, from the rightmost digit to the leftmost."""
    passes = 0
    for pos in range(len(codes[0])):
        codes = counting_pass(codes, pos)
        passes += 1
    return codes, passes


# Three-digit codes make each pass easy to follow
tiny = ["321", "123", "312", "132", "213", "231"]
step = tiny
for pos in range(3):
    step = counting_pass(step, pos)
    print(f"after digit {pos} (from the right):", step)

# Six-digit routing codes
routing = ["560001", "110011", "400076", "560001", "411001", "110001", "400001", "600042"]
result, passes = radix_sort_codes(routing)
print(result)
print("passes:", passes, "| matches sorted():", result == sorted(routing))

after digit 0 (from the right): ['321', '231', '312', '132', '123', '213']
after digit 1 (from the right): ['312', '213', '321', '123', '231', '132']
after digit 2 (from the right): ['123', '132', '213', '231', '312', '321']
['110001', '110011', '400001', '400076', '411001', '560001', '560001', '600042']
passes: 6 | matches sorted(): True

Watch the tiny example. After the first pass the codes are ordered by their last digit only. After the second, they are ordered by their last two digits (312, 213, 321, ...). After the third, by all three. Each pass is O(n + 10), and there are d passes for d-digit codes, so the total is O(d(n + b)) for base b. If the code width d is a small constant, that is linear in n.

When O(n) sorting is legitimate

The pattern is simple: the extra term k (or d x b) has to be small compared with n log n. If you can state a tight upper bound on the keys, a non-comparison sort is on the table. If you cannot, it is not. Variable-length keys such as names can be radix sorted too, but only with extra care for the padding, and the gain disappears for long strings.

Common mistakes

• Sizing the count array by the largest key without checking it. Symptom: MemoryError or an apparent hang when one stray value like 4,000,000,000 appears in the data. Validate the range first or fall back to sorted().
• Negative keys. Symptom: no error, wrong placement, because counts[-1] quietly addresses the last slot. Shift the keys by the minimum before counting.
• An unstable pass inside radix sort. Symptom: output is ordered only by the most recently processed digit, and ties come out scrambled. Each pass must keep equal digits in their existing order, as appending to buckets does.
• Unequal-length codes in radix sort. Symptom: IndexError: string index out of range for a shorter code, or silently wrong order. Left-pad the codes to a common width first.
• Returning keys instead of records. Symptom: the ratings are sorted but reviewer names are gone. Counting sort must move the whole record, which is why the placement loop uses review, not rating.

How this shows up in real projects and interviews

Counting is everywhere in real code, even when nobody calls it sorting: histograms, ranking by small integer scores, bucketing events by hour of day, sorting ages or grades, and "sort an array of 0s, 1s and 2s" (the Dutch national flag problem). Radix sort is the engine behind sorting fixed-width integer keys in some libraries and behind suffix-array style tricks. In interviews, the standard follow-up to "can you sort faster than n log n?" is exactly this lesson: yes, if the keys are bounded integers, here is the O(n + k) version, and here is when k makes it a bad idea. Say the assumption out loud, because the assumption is the answer. For the same "trade memory for time" reasoning in a different setting, see the hash tables material in Data Structures.