Counting sort, radix sort and bucket sort

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Minimum worst-case comparisons to sort 6 elements? from Lesson 3.3.1
• Which sorts are stable? from Lesson 3.1.2
• Expected probes for an unsuccessful search, α = 0.5? from Lesson 2.2.3

1 · The Hook

🎣

Sorting exam marks between 0 and 100 for a million students does not need comparisons at all: count how many students got each mark, then write the marks out in order. That is counting sort, linear time. Repeat it digit by digit and you get radix sort. Both rely on knowing something about the keys.

2 · Predict First

🤔

Keys [2, 5, 3, 0, 2, 3, 0, 3] all lie in 0 … 5. Count how many times each value occurs, then read the counts in order. What sorted array do you get, and how much work was it?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Counts: 0 → 2, 1 → 0, 2 → 2, 3 → 3, 4 → 0, 5 → 1 → [0, 0, 2, 2, 3, 3, 3, 5]. One pass to count (n), one pass over the k + 1 counts: Θ(n + k).

Counting sort (keys 0 … k)

• C[v] = number of keys equal to v.

• Prefix sums: C[v] = number of keys ≤ v (the last position for v, 1-based).

• Scan the input from the right; place each key x at position C[x] and decrement C[x].

• Time Θ(n + k); extra space Θ(n + k).

• Stable (thanks to the right-to-left placement): essential for radix sort.

• Useful when k = O(n).

Predict example: counts [2, 0, 2, 3, 0, 1] → prefix sums [2, 2, 4, 7, 7, 8].

Radix sort (LSD)

Sort d-digit numbers by the least significant digit first, using a stable sort (counting sort) for each digit, then the next digit, and so on.

• Time Θ(d · (n + b)) for base b (b = 10 for decimal digits).
• Correct only because each digit pass is stable: ties on the current digit keep the order from earlier passes.

Example: [329, 457, 657, 839, 436, 720, 355]

• by units: [720, 355, 436, 457, 657, 329, 839]
• by tens: [720, 329, 436, 839, 355, 457, 657]
• by hundreds: [329, 355, 436, 457, 657, 720, 839]

Bucket sort

Keys uniformly distributed in [0, 1): make n buckets, put key x in bucket ⌊n·x⌋, sort each bucket (insertion sort), concatenate. Average Θ(n); worst Θ(n²) if all keys land in one bucket.

Why they beat n log n

They read the keys' digits or values instead of comparing pairs, so the decision-tree bound does not apply.

4 · Visual

Counting sort, keys 0..5, input [2, 5, 3, 0, 2, 3, 0, 3]

value:     0  1  2  3  4  5
count:     2  0  2  3  0  1
prefix:    2  2  4  7  7  8      <- last position (1-based) for each value

scan right to left: 3 -> position 7, 0 -> 2, 3 -> 6, 2 -> 4, 0 -> 1, 3 -> 5, 5 -> 8, 2 -> 3
output:   [0, 0, 2, 2, 3, 3, 3, 5]

5 · Worked Examples

Example 1 Easy

Counting sort on n = 1,000 keys in the range 0 … 99. Time?

Solution

Θ(n + k) = Θ(1000 + 100) = Θ(n).

Example 2 Medium

Radix sort of n six-digit decimal numbers. Number of counting-sort passes and total time?

Solution

6 passes, Θ(6(n + 10)) = Θ(n).

Example 3 GATE

Why must each pass of LSD radix sort be stable?

Solution

So that numbers equal in the current digit stay ordered by the less significant digits sorted in earlier passes; an unstable pass would destroy that order.

6 · GATE Traps

⚠️

• Counting sort is linear only when k = O(n); for k = n² it is Θ(n²).
• Radix sort processes the least significant digit first (LSD) and needs a stable digit sort.
• Bucket sort's linear time is average under a uniform-distribution assumption.
• None of these is in-place in its standard form.

7 · Memory Hook

🧠

"Count, prefix, place from the right." Then radix = counting sort per digit, smallest digit first.

8 · Connect the Dots

Sorting is finished. The last lesson of Phase 3 asks a cheaper question: not the whole order, only the minimum, the maximum, the second largest or the k-th smallest.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksPrefix sums

Counting sort on [1, 4, 1, 2, 7, 5, 2] with keys 0 … 7. What is C[4] after the prefix-sum step (number of keys ≤ 4)?

Numerical answer: ________

Q2MCQ1 markRadix pass

After the first (units) pass of LSD radix sort, [170, 45, 75, 90, 802, 24, 2, 66] becomes:

• (A) [802, 2, 24, 45, 66, 170, 75, 90]
• (B) [2, 24, 45, 66, 75, 90, 170, 802]
• (C) [170, 90, 2, 802, 24, 45, 75, 66]
• (D) [170, 90, 802, 2, 24, 45, 75, 66]

Q3NAT1 markPasses

LSD radix sort on 32-bit integers using base 256 (one byte per digit). Number of passes?

Numerical answer: ________

Q4MSQ2 marksCounting sort facts

Which are true?

• (A) Counting sort is stable when placed right-to-left.
• (B) Counting sort is efficient when k is much larger than n.
• (C) Counting sort compares keys.
• (D) Counting sort runs in Θ(n + k) time.

Q5NAT2 marksRadix result

LSD radix sort on [329, 457, 657, 839, 436, 720, 355]. After the tens pass, which number is first?

Numerical answer: ________

10 · Rule Card

• Counting sort: counts, prefix sums, place right-to-left; Θ(n + k); stable; needs k = O(n).
• LSD radix: stable digit sorts, least significant first; Θ(d(n + b)).
• Bucket sort: uniform keys, average Θ(n), worst Θ(n²).
• Non-comparison sorts escape the n log n bound.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

counting sortprefix sums of countsstable placementradix sort (LSD)digit passes d(n + b)bucket sortnon-comparison sorting

12 · Answer Vault