Radix sort — LSD, MSD; O(d(n+k)): Question bank

Before we start, one shared vocabulary reminder so no symbol is unearned:

True or false — justify

Radix sort escapes the

Ω (n lo g n)

comparison lower bound

True — it never asks "is

a < b

?" between whole keys, so the Comparison Sort Lower Bound (which only binds comparison sorts) simply does not apply.

LSD radix sort with an unstable per-digit sort still ends up correct

False — stability is the load-bearing assumption of the induction; without it, ties on the current digit can scramble the order earlier passes built, and correctness collapses.

Radix sort is always

O (n)

False —

d = ⌊ lo g_{k} M ⌋ + 1

hides a logarithm; if keys grow like

n^{c}

then

d = Θ (lo g n)

and the cost returns to

Θ (n lo g n)

Making the radix

k

larger always makes radix sort faster

False — bigger

k

cuts the pass count

d

but inflates the

O (k)

count array; past

k \approx n

the

+ k

term dominates and you lose, so there is a sweet spot near

k \approx n

MSD radix sort must examine every digit of every key, just like LSD

False — MSD can stop a bucket as soon as it holds

\leq 1

element, so a distinguishing prefix (e.g. the first letter of "apple" vs "zebra") is enough; LSD alone reads all

d

digits.

Counting sort inside each pass could be replaced by quicksort without changing correctness

False for LSD — quicksort is not stable, and LSD requires stability; you would also reintroduce comparisons, defeating the purpose (see Counting Sort).

The space cost of radix sort is

O (n + k)

True — one output array of size

n

plus one count array of size

k

; nothing else scales, so the total auxiliary space is

O (n + k)

Radix sort works on negative integers with no modification

False — digit extraction

(x div exp) mod k

assumes non-negative keys; negatives need an offset (add a bias) or a signed-aware final pass, or they sort into wrong positions.

Both LSD and MSD can be made stable

True — LSD is stable by construction; MSD is stable too if each bucket preserves input order and buckets are concatenated in radix order (see Stability in Sorting).

Radix sort and Bucket Sort are the same algorithm

False — bucket sort distributes by value range then sorts each bucket; radix sort distributes by one digit repeatedly using a stable count. They share the "scatter into buckets" idea but differ in the key they bucket on.

Spot the error

"I ran LSD placement left-to-right instead of right-to-left; order is fine."

Wrong — walking the input left-to-right while decrementing the prefix-count reverses ties, breaking stability; you must iterate the input in reverse for the pass to stay stable.

"My prefix-sum loop is for i in range(k): count[i] += count[i]."

Wrong — it must add the previous bucket: count[i] += count[i-1]; adding count[i] to itself just doubles a value and produces garbage offsets.

d

is the number of elements, so more data means more passes."

Wrong —

d

is the number of digit positions of the largest key

M

, not

n

; adding more elements of the same width does not add passes.

"Radix sort compares digits, so it's still a comparison sort."

Wrong — it never compares two digits to decide order; it indexes by digit value into a count array, which is why the comparison lower bound does not apply.

"I chose

k = 2

(binary) to make the count array tiny and it's the fastest choice."

Wrong —

k = 2

maximizes

d = ⌊ lo g_{2} M ⌋ + 1

, so you do the most passes possible; tiny

k

trades a small count array for a huge pass count and is usually slowest.

"MSD gives me sorted order after processing just the first digit."

Wrong — only the top-level order is fixed after digit 0; within each bucket the elements are still unsorted until the recursion descends further.

"I wrote (x / exp) % k with a single slash to grab a digit."

Wrong — single / is real (float) division, so you get a fraction and the modulo misbehaves; you need integer division // (i.e. floor division) to isolate a clean digit.

Why questions

Why must LSD start from the least significant digit, not the most?

Because the most significant digit dominates value: sorting it last (with stability preserving all lower-digit work) lets the final pass impose the correct top-level order while ties fall back to already-sorted lower digits.

Why does stability alone guarantee correctness in the LSD induction?

Because keys equal on the current (higher) digit keep their prior relative order, and that prior order was already correct on all lower digits — so no already-done work is ever undone.

Why is one counting-sort pass

O (n + k)

and not

O (n)

The tally and placement loops are

O (n)

, but zeroing and prefix-summing the count array touches all

k

buckets, adding a

+ k

term that matters when

k

is large relative to

n

Why does MSD suit variable-length strings better than LSD?

MSD reads keys front-to-back and can stop once a prefix distinguishes them, so short-but-different strings need little work; LSD must align on a fixed width and read every character (see Tries for the same prefix idea).

Why doesn't radix sort violate the comparison lower bound theorem?

The theorem only lower-bounds comparison-based sorts; radix sort extracts information from key structure via indexing, a channel the theorem never accounts for (see Big-O Notation and Comparison Sort Lower Bound).

Why pick

k = 256

for 32-bit integers?

One byte per pass gives

d = 32/8 = 4

passes and a 256-entry count array that is negligible beside large

n

— a balance between few passes and a small count array.

Edge cases

What does radix sort do with an empty array?

Returns it unchanged — the loop bound maxv // exp > 0 is never entered (there is no max

M

), so zero passes run, which is correct.

What happens when all keys are identical?

Every pass drops them all into a single bucket and stability keeps their input order; the result equals the input, which is trivially sorted — no wasted correctness, just

d

full passes of work.

How many passes for a single-element array or all single-digit keys?

Exactly

d = 1

pass, since

M < k

gives

⌊ lo g_{k} M ⌋ + 1 = 1

so only the units position exists; the loop runs once and stops.

What if some keys have fewer digits than the max (e.g. 2 among 802)?

Missing high-order digits are treated as

0

(x div exp) mod k

, so shorter keys land in bucket

0

on those passes and correctly sort as smaller — no padding needed.

What is

d

when

M

is exactly a power of

k

, say

M = 1000, k = 10

d = ⌊ lo g_{10} 1000 ⌋ + 1 = 3 + 1 = 4

because

1000

has four digits (the leading 1 plus three zeros); using 3 would drop that top digit and misplace

1000

. Note

⌈ lo g_{10} 1000 ⌉ = 3

is the wrong formula here — always use

⌊ lo g_{k} M ⌋ + 1

Active Recall

Recall One-line answers to the four core traps

Stable? :: So ties on the current digit keep the order earlier passes already sorted. $d$ ? :: $⌊ lo g_{k} M ⌋ + 1$ , the digit-count of the biggest key $M$ . MSD wins? :: On variable-length keys where a short prefix separates most elements. Always $O (n)$ ? :: No — if keys are as large as $n^{c}$ , $d = Θ (lo g n)$ .