Counting, Radix, and Bucket Sort

Every sort so far — quicksort, heap sort, merge sort — decides order by comparing two elements at a time. There’s a proven floor on how fast that can ever go:

$$\Omega(n \log n)$$

is the best any comparison-based sort can guarantee, because sorting must distinguish between $n!$ possible orderings, and each comparison only answers a yes/no question — you need $\log_2(n!) = \Theta(n \log n)$ of them in the worst case. Counting, radix, and bucket sort sidestep this entirely: they never compare two elements to each other. Instead they use the values themselves — as array indices — which unlocks $O(n)$-ish time, if the keys are the right shape (bounded integers, or a range you can bucket).

What you’ll learn

• Counting sort: count occurrences, prefix-sum them into positions, place elements directly — $O(n + k)$, and stable if done carefully.
• Radix sort (LSD): repeatedly counting-sort by one digit at a time, least-significant first, to sort integers of any size in linear time.
• Bucket sort: scatter into ranged buckets, sort each bucket small, then concatenate — great for uniformly distributed values.
• When each one is (and isn’t) the right tool.

The cue

These never appear on LeetCode under their own names. They appear disguised.

You are looking at a linear-time sort when…

• You need to sort by frequency, and a frequency cannot exceed n — so bucket by count and read down. LC 347, 451, 692.
• The values are a permutation of 1..n, or otherwise bounded by n — then the index is the key. That is counting sort’s idea, and it is what cyclic sort is. LC 41, 268, 448.
• The keys are small integers, characters, or fixed-width strings — ages, scores 0-100, dates, DNA bases. The alphabet is tiny and known.
• The problem says “in $O(n)$” about sorting, which is impossible in the comparison model — so it is telling you the keys are bounded.
• Values are uniformly distributed over a known range — bucket sort’s precondition, and the one most easily violated.

When it is the wrong tool. Arbitrary comparable objects, unbounded integers, or floats with no known range: $\Omega(n \log n)$ applies and you use sorted(). Counting sort with a huge value range allocates an array the size of that range — sorting [1, 10**9] needs a billion counters for two elements. And bucket sort degrades to its inner sort’s bound when the distribution is skewed, which is the failure mode below.

Counting sort: count, then place

Counting sort works when every value is a small non-negative integer in a known range 0..k. The idea: count how many times each value appears, turn those counts into prefix sums (so count[v] becomes “how many elements are $\le v$”), and use that number as each element’s landing spot in the output.

counting_sort.py

def counting_sort(arr):
    if not arr:
        return arr
 
    k = max(arr)                # values are 0..k
    count = [0] * (k + 1)
    for x in arr:
        count[x] += 1
 
    for i in range(1, k + 1):
        count[i] += count[i - 1]   # count[v] = number of elements <= v
 
    output = [0] * len(arr)
    for x in reversed(arr):        # reversed = keeps equal elements stable
        count[x] -= 1
        output[count[x]] = x
 
    return output
 
 
arr = [4, 2, 2, 8, 3, 3, 1]
print("input: ", arr)
print("sorted:", counting_sort(arr))

Three linear passes over the data (count, prefix-sum, place) — no comparisons anywhere. That’s the whole $O(n + k)$: $n$ for the array, $k$ for the count array covering the value range.

Why iterate in reverse for stability

Walking the input backwards while placing into output means that if two equal values x appear at positions i < j in the input, j gets placed (and count[x] decremented) before i does — so i lands at the lower of the two available slots for value x, preserving their original relative order. Skip the reversal (or iterate forward) and counting sort still sorts correctly, but loses stability.

Watch counting sort place each element

sketch Counting sort: prefix-sum positions, placed in reverse p5.js Pause Restart

Prefix-summed counts give each value its landing index. Scanning the input in reverse and decrementing count[x] before placing keeps equal values in their original order -- this is what makes counting sort stable.

Radix sort: counting sort, one digit at a time

Counting sort’s weakness: if the values span a huge range (say, up to a billion), k is huge and the count array becomes impractically large. Radix sort fixes that by never counting-sorting on the whole value — only on one digit at a time (base 10, so each digit only needs a count array of size 10), starting from the least significant digit (LSD) and working toward the most significant.

radix_sort.py

def counting_sort_by_digit(arr, exp):
    """Stable counting sort keyed on the digit at place value `exp`
    (exp = 1 for ones, 10 for tens, 100 for hundreds, ...)."""
    n = len(arr)
    output = [0] * n
    count = [0] * 10
 
    for x in arr:
        digit = (x // exp) % 10
        count[digit] += 1
 
    for i in range(1, 10):
        count[i] += count[i - 1]
 
    for x in reversed(arr):        # reversed again -- stability matters here too
        digit = (x // exp) % 10
        count[digit] -= 1
        output[count[digit]] = x
 
    return output
 
 
def radix_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr
 
 
nums = [170, 45, 75, 90, 802, 24, 2, 66]
print("sorted:", radix_sort(nums))

LSD radix sort only works because each pass is stable

Sorting by the ones digit, then the tens digit, then the hundreds digit only produces a fully sorted array because every pass is stable: when the tens-digit pass sees two numbers that tie on the tens digit, it must preserve the order the previous (ones-digit) pass already established between them. Swap in an unstable per-digit sort and radix sort silently produces garbage. This is the one place stability isn’t just a nice-to-have — it’s load-bearing correctness.

For $d$ digits and $n$ numbers, that’s $d$ passes of an $O(n + 10)$ counting sort each — $O(d \cdot n)$ total, which is linear in $n$ for any fixed number of digits (i.e., fixed-width integers, like 32-bit or 64-bit).

Bucket sort: scatter, sort small, concatenate

Bucket sort targets values uniformly spread across a known range (the classic case: floats in [0, 1)). Scatter each value into one of k equal-width buckets by its magnitude, sort each (small) bucket with whatever comparison sort you like, then concatenate the buckets in order.

bucket_sort.py

def bucket_sort(arr, bucket_count=10):
    if not arr:
        return arr
 
    buckets = [[] for _ in range(bucket_count)]
    for x in arr:
        idx = int(x * bucket_count)
        idx = min(idx, bucket_count - 1)   # guard x == 1.0 landing out of range
        buckets[idx].append(x)
 
    for b in buckets:
        b.sort()   # each bucket is small -- even O(n^2) insertion sort is fine here
 
    result = []
    for b in buckets:
        result.extend(b)
    return result
 
 
data = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
print("sorted:", bucket_sort(data))

If the input really is uniformly distributed, every bucket ends up with roughly n / k elements, so sorting all buckets costs $O(n)$ total on average — the $O(n \log n)$ (or worse) inner sorts are each working on a tiny slice. If the data is instead heavily clustered into one bucket, you’re back to sorting almost the whole array with one comparison sort, and the worst case becomes $O(n^2)$.

When these are (and aren’t) the right tool

• Counting sort: values are small non-negative integers with a known, small range k (e.g., ages, grades, byte values 0-255). Bad idea if k is huge relative to n — you’d allocate a giant, mostly-empty array.
• Radix sort: fixed-width integers (or strings treated digit-by-digit) of any magnitude — the digit count d stays small (10 for a billion) even when the values themselves are huge.
• Bucket sort: values you know are roughly uniformly distributed over a range — floats in [0, 1), timestamps spread across a day, etc. Clustered/skewed data defeats it.
• None of these three handle arbitrary comparable objects (strings by dictionary order, custom objects) as directly as sorted() does — that’s what the next lesson, Timsort and custom sorting, covers.

Dry run

Counting sort on [4, 2, 2, 8, 3, 3, 1]

Stage	State
counts (by value)	{1: 1, 2: 2, 3: 2, 4: 1, 8: 1}
prefix sums	[1, 3, 5, 6, 6, 6, 6, 7]
output	[1, 2, 2, 3, 3, 4, 8]

The prefix array is the whole algorithm. prefix[k] is “how many elements are $\le k$”, so it is also the index one past where the last k belongs. Decrementing it as you place each element walks backwards through that value’s block.

Note the counter array has max - min + 1 = 8 slots for 7 elements — and a negative range works identically by offsetting: [-3, 0, -1, 2] sorts to [-3, -1, 0, 2]. The - lo offset is what makes negatives legal, and forgetting it is an IndexError on the first negative value.

Counting sort’s stability depends on one loop direction

Sorting [(1,'a'), (0,'b'), (1,'c'), (0,'d')] by the first element:

Placement pass	Result	Stable?
for item in reversed(a)	[(0,'b'), (0,'d'), (1,'a'), (1,'c')]	yes
for item in a	[(0,'d'), (0,'b'), (1,'c'), (1,'a')]	no

Verified. Iterating backwards over the input is what makes counting sort stable, and it is easy to write forwards without noticing — the output is still correctly sorted, just with equal elements reversed.

The reason: the prefix counter for a value is decremented from the end of that value’s block towards the start. So the element you place first goes last. Walking the input in reverse means the last equal element is placed first, landing at the end — preserving the original order.

This is not a footnote. Radix sort is built entirely on repeated counting sorts, and it is correct only if each pass is stable. Get this direction wrong and radix sort produces garbage.

Radix sort on [170, 45, 75, 90, 802, 24, 2, 66]

Least-significant digit first, base 10:

Pass	Sorted by	Array after
1s	ones digit	[170, 90, 802, 2, 24, 45, 75, 66]
10s	tens digit	[802, 2, 24, 45, 66, 170, 75, 90]
100s	hundreds digit	[2, 24, 45, 66, 75, 90, 170, 802]

Look at pass 2’s output: [802, 2, 24, 45, 66, 170, 75, 90]. That is not sorted, and it is not supposed to be — it is sorted by the last two digits (02, 02, 24, 45, 66, 70, 75, 90). Each pass sorts by one more digit, and the earlier passes’ work survives because counting sort is stable. Within the tens-digit group 70, both 170 and 75… note 170 precedes 75 because their tens digits are 7 and 7, and 170 came earlier after pass 1. Pass 3 then separates them by hundreds.

That is the entire correctness argument for radix sort, and it is why the stability drill above matters: an unstable inner sort destroys the previous pass’s ordering and the result is wrong.

Bucket sort, and when it collapses

Six uniformly-spread floats, six buckets:

text

[0.42, 0.32, 0.75, 0.11, 0.99, 0.53]  ->  [0.11, 0.32, 0.42, 0.53, 0.75, 0.99]

Now the skewed case, [1, 1, 1, 1, 1, 1000] into six buckets over the range 1-1000:

Bucket	0	1	2	3	4	5
Occupancy	5	0	0	0	0	1

The answer is still correct — [1, 1, 1, 1, 1, 1000] — but five of six elements land in one bucket, so that bucket’s inner sort does all the work and the total is the inner sort’s bound, $O(n \log n)$. Bucket sort’s $O(n)$ claim rests entirely on the assumption that elements spread evenly, and nothing in the algorithm enforces or detects that.

This is the honest way to state it: bucket sort is $O(n + k)$ expected, under a uniformity assumption, and $O(n \log n)$ when the assumption fails. Unlike quicksort’s randomised pivot, there is no cheap fix — the distribution is a property of the data.

Complexity at a glance

Sort	Time	Space	Stable?	Needs
Counting sort	$O(n + k)$	$O(n + k)$	Yes (with reverse-scan placement)	small integer range k
Radix sort (LSD)	$O(d(n + b))$	$O(n + b)$	Yes	fixed-width integers, d digits, base b
Bucket sort	$O(n + k)$ avg, $O(n^2)$ worst	$O(n + k)$	Depends on the inner sort	roughly uniform distribution

k = value range (counting sort) or bucket count (bucket sort); d = number of digits; b = digit base (10 for decimal digits).

The variant map

Variant	The mechanism	Canonical problem
Sort small bounded integers	Counting sort, max - min + 1 counters	ages, scores, LC 912 with bounded values
Sort by frequency	Bucket by count (a count cannot exceed n), read from n down	347 · 451 · 692
k most frequent in $O(n)$ worst case	Same buckets, stop after k — beats the heap’s $O(n \log k)$	347
Values are a permutation of 1..n	Use the index as the key — cyclic sort	41 · 268 · 448 · 442
Sort fixed-width strings	Radix sort, one character position per pass	—
Sort large integers	Radix in base $2^{16}$ or $2^{32}$: fewer passes, bigger counters	CP
Sort floats in a known range	Bucket sort, then insertion-sort each bucket	—
Sort by multiple keys	Radix’s idea generally: sort by the least significant key first, relying on stability	any stable multi-key sort
Colours / three distinct values	Counting sort in one pass, or Dutch-flag partition in place	75 Sort Colors
Sort a nearly-sorted array	None of these — insertion sort or Timsort	—

The multi-key trick is radix sort’s real lesson

To sort by “department ascending, then salary descending”, you can sort twice: first by salary descending, then by department ascending. If the second sort is stable, the salary order survives within each department.

That is radix sort’s argument applied to arbitrary keys, and it is verified on the Timsort page: two stable passes give exactly the same result as one tuple key. It is the technique to reach for when one of the keys cannot be negated — strings, for instance, where -x is not available.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 1122 — Relative Sort Array · Easy

Problem. Sort arr1 so that its elements follow the relative order given by arr2. Elements not present in arr2 go at the end, in ascending order.

Constraints. 1 <= len(arr1), len(arr2) <= 1000, 0 <= values <= 1000, arr2 has distinct values, all of which appear in arr1.

Examples. arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] gives [2,2,2,1,4,3,3,9,6,7,19]

pch.exerciseTag pch.exerciseTitle

Editorial

Converting “this arbitrary order” into a numeric rank turns the problem into a standard sort. The tuple key then layers the fallback rule on top.

Time $O(n \log n)$. Space $O(n)$.

rank.get(v, len(arr2)) is doing two jobs: it supplies the rank for known values, and it assigns unknown values a rank strictly larger than every known one, so they sort last. The second tuple component then orders them ascending among themselves — which is exactly what the problem asks.

Because values are bounded by 1000, a counting sort is the $O(n + 1000)$ alternative and the direct connection to this page: tally arr1, then emit values in arr2’s order followed by the remaining values in ascending index order. That avoids comparison sorting entirely.

[28,6,22,8,44,17] shows the fallback: 17 and 44 are unranked and appear at the end in ascending order.

Follow-ups: “Do it with counting sort?” — the bounded-range version above; the expected answer on this page. “What if arr2 had values absent from arr1?” — the rank map is unaffected. “Descending fallback?” — negate the second key component.

LC 274 — H-Index · Medium

Problem. Given citation counts for a researcher’s papers, return their h-index: the largest h such that at least h papers have at least h citations each.

Constraints. 1 <= len(citations) <= 5000, 0 <= citations[i] <= 1000.

Examples. [3,0,6,1,5] gives 3 · [1,3,1] gives 1 · [100] gives 1

pch.exerciseTag pch.exerciseTitle

Editorial

The key observation is that the h-index cannot exceed the number of papers, so any citation count above n is indistinguishable from n for this purpose. That caps the value range at n + 1, which is exactly the condition counting sort needs.

Time $O(n)$. Space $O(n)$.

Walking h downward and accumulating gives “how many papers have at least h citations” without re-scanning: each step adds the papers with exactly h. The first h where the running total reaches h is the answer, and because we come down from the top it is the largest such h.

[100] giving 1 is the capping case: one paper with 100 citations still yields an h-index of only 1, since there is only one paper. [0] and [0,0] give 0.

The $O(n \log n)$ answer — sort descending and find the last index where citations[i] >= i + 1 — is simpler and worth stating first. The counting version is the improvement this page exists to teach.

Follow-ups: “Input already sorted (LC 275)?” — binary search for the crossover in $O(\log n)$. “Why cap at n?” — the bound argument; this is the expected question. “What is the g-index?” — a related metric using cumulative citations, solvable the same way.

LC 164 — Maximum Gap · Medium

Problem. Return the maximum difference between two successive elements in the array’s sorted form. If the array has fewer than two elements, return 0. Aim for linear time and space.

Constraints. 1 <= len(nums) <= 10^5, 0 <= nums[i] <= 10^9.

Examples. [3,6,9,1] gives 3 · [10] gives 0

pch.exerciseTag pch.exerciseTitle

Editorial

Sorting and scanning adjacent pairs is $O(n \log n)$ and accepted. Start there.

Time $O(n \log n)$ as written. Space $O(1)$ beyond the sort.

The problem asks for linear time, and the route is a pigeonhole / bucket argument worth understanding:

With n values spanning max - min, the average gap is (max - min) / (n - 1). The maximum gap must be at least the average, so if you create buckets of exactly that width, no two values inside a single bucket can be the maximum gap apart — meaning the answer always spans a boundary between buckets.

So you only need each bucket’s minimum and maximum, then take the largest difference between one bucket’s max and the next non-empty bucket’s min. That is $O(n)$ time and $O(n)$ space, with no sorting.

Radix sort is the other linear option: values are bounded by $10^9$, so a handful of digit passes sorts them in $O(n)$.

[1,1,1] giving 0 (all equal) and [10] giving 0 (single element) are the degenerate cases the guard exists for.

Follow-uups: “Achieve $O(n)$?” — the bucket argument above, or radix sort; this is the expected follow-up. “Why is the max gap at least the average?” — if every gap were below average their total would be below max - min, a contradiction. “Negative values?” — the constraints exclude them, but the argument is unchanged.

Practice

Linear-time sorts appear on LeetCode disguised as something else: bucketing by frequency (347, 451), and using the index as the key when values are a permutation of 1..n (cyclic sort). Those are the problems below.

11 problems

3 easy7 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○268Missing NumbereasyNeetCode 150Blind 75
• ○448Find All Numbers Disappeared in an Arrayeasy
• ○1051Height Checkereasy
• ○347Top K Frequent ElementsmediumNeetCode 150Blind 75amazonmetauberbytedance
• ○147Insertion Sort Listmedium
• ○215Kth Largest Element in an ArraymediumNeetCode 150LeetCode Top Interview 150
• ○287Find the Duplicate NumbermediumNeetCode 150
• ○451Sort Characters By Frequencymedium
• ○912Sort an Arraymedium
• ○973K Closest Points to OriginmediumNeetCode 150
• ○41First Missing Positivehard

Interview follow-ups

They ask	What they’re checking	The answer
“Sorting is $\Omega(n \log n)$. How can this be $O(n)$?”	Whether you know which model	The bound applies to comparison sorts. These do not compare elements to each other — they use the key as an array index, which is more information than a comparison gives. Leaving the model is the only way to beat the bound
“What is counting sort’s real complexity?”	Naming both variables	$O(n + k)$ where k is the value range, and $O(k)$ space. For [1, 10**9] that is a billion counters for two elements — so the bound is only good when k is comparable to n
“Why iterate the input backwards when placing?”	The stability mechanism	The prefix counter walks backwards through each value’s block, so the element placed first lands last. Reversing the input makes the last equal element get placed first, preserving order. Verified: forwards gives [(0,'d'),(0,'b'),…] instead of [(0,'b'),(0,'d'),…]
“Does stability matter for plain integers?”	Whether you see the dependency	Not for the integers themselves — but radix sort is built on repeated counting sorts and is correct only if each is stable. Get the direction wrong and radix produces a wrong answer
“Why does radix sort go least-significant digit first?”	The invariant	Each pass sorts by one more digit and relies on stability to preserve the previous passes’ order. Pass 2’s output [802, 2, 24, 45, 66, 170, 75, 90] is not sorted — it is sorted by the last two digits, which is exactly right
“Radix sort’s complexity?”	The hidden factor	$O(d(n + b))$ for d digits in base b. It is linear in n but d depends on the value range: $d = \log_b(\max)$. So it is not magically better than $n \log n$ for arbitrary integers — the $\log$ moved into d
“When does bucket sort fail?”	The assumption	Skewed data. Measured: [1,1,1,1,1,1000] puts 5 of 6 elements in one bucket, so that bucket’s inner sort does all the work and the total is $O(n \log n)$. Unlike a randomised pivot, there is no cheap fix — the distribution belongs to the data
“LC 347, top k frequent — your approach?”	Recognising the disguise	Bucket by frequency: a count cannot exceed n, so index buckets by count and walk down from n. $O(n)$ worst case, no randomisation, and simpler than the heap’s $O(n \log k)$
“Sort by department ascending then salary descending, where department is a string”	The multi-key trick	Two stable passes: salary descending first, then department ascending. Stability preserves the first pass within each group — radix sort’s argument, applied when a key cannot be negated
“Values are a permutation of 1..n. Anything better?”	The strongest version	Cyclic sort — place each value at index value - 1 by swapping. $O(n)$ time and $O(1)$ space, no counter array at all. That is LC 41, 268, 448
“Sort 32-bit integers with radix. What base?”	Practical tuning	Base $2^{16}$: two passes with 65,536 counters, versus ten passes in base 10. Larger base means fewer passes and more memory — the trade is d against b

Self-check

pch.quizTag pch.quizDefaultTitle

1. Sorting is proved to be Omega(n log n). How do counting and radix sort achieve O(n)?

   A They are only O(n) on average B The bound applies to COMPARISON sorts; these use the key as an array index, which is strictly more information than a comparison C They use extra memory, which changes the bound D The proof is wrong for small inputs
   pch.quizShowAnswer

   B — The bound applies to COMPARISON sorts; these use the key as an array index, which is strictly more information than a comparison — A comparison yields one bit -- "is a < b" -- and the information-theoretic argument counts how many bits you need to distinguish n! orderings. Using a value directly as an index sidesteps that entirely. Extra memory alone does not buy anything; merge sort uses O(n) and is still bound by the comparison limit.

2. What is counting sort's complexity, and why does that limit its use?

   A O(n) time and O(n) space, always B O(n + k) time and O(k) space where k is the VALUE RANGE -- so [1, 10**9] needs a billion counters for two elements C O(n log k) D O(n) time and O(1) space
   pch.quizShowAnswer

   B — O(n + k) time and O(k) space where k is the VALUE RANGE -- so [1, 10**9] needs a billion counters for two elements — The counter array is indexed by value, so its size is max - min + 1 regardless of how many elements there are. That is the whole precondition: k must be comparable to n. In the traced example 8 counters served 7 elements, which is the regime where it wins.

3. Counting sort's placement loop iterates over the input in REVERSE. What breaks if you iterate forwards?

   A The output is no longer sorted B It stays sorted but loses stability -- equal elements come out in reverse order C It raises an IndexError D Nothing changes
   pch.quizShowAnswer

   B — It stays sorted but loses stability -- equal elements come out in reverse order — Verified: reversed gives [(0,'b'),(0,'d'),(1,'a'),(1,'c')] and forwards gives [(0,'d'),(0,'b'),(1,'c'),(1,'a')]. Both are sorted by key. Because the prefix counter decrements from the end of each value's block, the first element placed ends up last -- so you must feed the input backwards. And this is not cosmetic: radix sort is only correct if each counting pass is stable.

4. After radix sort's second pass, [170,45,75,90,802,24,2,66] has become [802, 2, 24, 45, 66, 170, 75, 90]. That is not sorted. Is something wrong?

   A Yes -- the second pass has a bug B No -- it is sorted by the last TWO digits (02, 02, 24, 45, 66, 70, 75, 90), and the third pass separates by hundreds C Yes -- radix sort should sort most-significant digit first D No, but only because the array contains a 2
   pch.quizShowAnswer

   B — No -- it is sorted by the last TWO digits (02, 02, 24, 45, 66, 70, 75, 90), and the third pass separates by hundreds — Each pass extends the sorted suffix of digits by one, and the earlier passes' work survives because counting sort is stable. Reading the last two digits of that array gives a sorted sequence. This is exactly why LSD radix needs a stable inner sort -- an unstable one would destroy the previous pass and the final answer would be wrong.

5. Radix sort is described as linear. What is the hidden factor?

   A The base b, which must be at least 10 B The digit count d: the bound is O(d(n + b)), and d = log_b(max), so the log has moved rather than vanished C The recursion depth D There is none -- it is genuinely O(n) for any integers
   pch.quizShowAnswer

   B — The digit count d: the bound is O(d(n + b)), and d = log_b(max), so the log has moved rather than vanished — For fixed-width keys d is a constant and radix is genuinely linear. For arbitrary integers d grows with the magnitude, so the log reappears as the number of passes. This is why choosing the base matters -- 32-bit integers take two passes in base 2^16 versus ten in base 10, trading counter memory for passes.

6. Bucket sort on [1, 1, 1, 1, 1, 1000] with six buckets over the range 1-1000. What happens?

   A It returns the wrong answer B Correct answer, but 5 of 6 elements land in one bucket, so that bucket's inner sort dominates and the total is O(n log n) C It raises a division error D The buckets are evenly filled because there are six elements
   pch.quizShowAnswer

   B — Correct answer, but 5 of 6 elements land in one bucket, so that bucket's inner sort dominates and the total is O(n log n) — Measured occupancy [5, 0, 0, 0, 0, 1]. Correctness never depended on the distribution -- only the complexity did. Bucket sort is O(n + k) *expected under uniformity*, and there is no cheap fix, because unlike a randomised pivot the distribution is a property of the data rather than of your choices.

7. LC 347 asks for the k most frequent elements. Why is bucketing better than a heap here?

   A It uses less memory B A frequency cannot exceed n, so buckets indexed by count give O(n) WORST case with no randomisation -- against the heap's O(n log k) C Heaps cannot handle ties D It is not better; the heap is optimal
   pch.quizShowAnswer

   B — A frequency cannot exceed n, so buckets indexed by count give O(n) WORST case with no randomisation -- against the heap's O(n log k) — The bounded key is what unlocks the linear sort: build n+1 buckets, drop each value into buckets[count], then walk down from n taking values until you have k. No comparisons, no log, and deterministic. Checking whether a key is bounded before reaching for a heap is the habit this page is really teaching.

8. You must sort by department ascending, then salary descending, and department is a string. What is the cleanest approach?

   A Negate the department string B Two stable passes: sort by salary descending first, then by department ascending -- stability preserves the salary order within each department C One pass with a cmp_to_key comparator, which is the only option D Sort by department, then sort each group separately
   pch.quizShowAnswer

   B — Two stable passes: sort by salary descending first, then by department ascending -- stability preserves the salary order within each department — This is radix sort's argument applied to arbitrary keys: sort by the least significant key first and let stability carry it. Strings cannot be negated, which rules out a single tuple key with a minus sign. A cmp_to_key comparator does work but is markedly slower, and sorting each group separately means finding the groups first -- more code for the same result.

Recall card

• These beat $\Omega(n \log n)$ by leaving the comparison model — they use the key as an index, which carries more information than a comparison.
• Counting sort is $O(n + k)$ time and $O(k)$ space in the value range. [1, 10**9] would need a billion counters for two elements.
• The prefix-sum array is the algorithm: prefix[v] = how many elements are $\le v$ = one past where the last v goes.
• Offset by - min so negative values work.
• Place by iterating the input BACKWARDS — that is what makes it stable. Forwards still sorts, but reverses equal elements. Verified.
• Radix sort is repeated counting sort, least-significant digit first, and it is correct only because each pass is stable. Intermediate output is sorted by the last d digits, not fully sorted.
• Radix is $O(d(n + b))$ — the log lives in d = \log_b(\max). Base $2^{16}$ sorts 32-bit ints in two passes.
• Bucket sort assumes uniformity. [1,1,1,1,1,1000] puts 5 of 6 in one bucket -> $O(n \log n)$. No cheap fix; the distribution belongs to the data.
• On LeetCode these appear disguised: bucket-by-frequency (347, 451), index-as-key / cyclic sort (41, 268, 448), three-value counting (75).
• Multi-key without negation: two stable passes, least significant first.

Recap

• Comparison sorts are stuck at $\Omega(n \log n)$ — a proven lower bound. Counting, radix, and bucket sort escape it by using key values directly as positions, never comparing elements to each other.
• Counting sort ($O(n + k)$): count, prefix-sum into positions, place in reverse for stability. Needs a small integer range k.
• Radix sort ($O(d(n+b))$): repeated stable counting sort, one digit at a time, LSD first — correctness depends on every pass being stable.
• Bucket sort ($O(n+k)$ average): scatter into ranged buckets, sort each small bucket, concatenate — shines on uniformly distributed data, degrades to $O(n^2)$ if the data clusters into one bucket.

Next: Timsort and Custom Sorting — how Python’s built-in sorted() and .sort() actually work, and how to sort arbitrary objects with key= and custom comparators.