You implement LSD radix sort but accidentally use an unstable sub-sort (equal-key elements may reorder arbitrarily). What is the consequence?
AThe algorithm runs faster because stability checking overhead is removed
BThe algorithm still sorts correctly for integers, but fails for strings
CLater digit passes destroy the relative ordering established by earlier passes, corrupting the final result
DThe algorithm crashes because it requires stable memory pointers
Stability is not a performance optimization — it is the correctness mechanism. When you sort by the tens digit, you must preserve the ordering by ones digit that the previous pass established. An unstable sub-sort scrambles equal-key elements arbitrarily, undoing that work. LSD radix sort is correct precisely because stability ensures each pass refines the ordering without disturbing previous passes. Replace the stable sub-sort with an unstable one and the algorithm produces incorrect results.
Question 2 Multiple Choice
You implement radix sort on 32-bit integers using base 256 (b = 256, so each digit represents one byte). How many passes over the data are required?
A32 passes — one per bit
B8 passes — one per pair of bits (nibble)
C4 passes — one per byte
D2 passes — one for the low 16 bits, one for the high 16 bits
In base 256, each 'digit' represents 8 bits (one byte). A 32-bit integer has 4 bytes, so 4 passes suffice, each scanning all n elements using a 256-entry counting array. Choosing base 256 is a deliberate optimization: it minimizes passes to 4 (versus 32 for base-2) while keeping the auxiliary array small. The general formula is d = (key width in bits) / log2(b).
Question 3 True / False
Radix sort achieves its linear-time performance by comparing elements directly, just more cleverly than comparison-based sorts like quicksort.
TTrue
FFalse
Answer: False
Radix sort is a non-comparison sort — it never compares two elements against each other. Instead, it inspects individual digits and places elements into buckets using counting sort. This is exactly why it can break the O(n log n) comparison-sort lower bound: that lower bound applies only to algorithms that determine order by comparing pairs of elements. Radix sort exploits the structure of the keys (they're sequences of digits) to sort without comparisons.
Question 4 True / False
Stability of the sub-sort is essential to the correctness of LSD radix sort — without it, the algorithm cannot guarantee a sorted result.
TTrue
FFalse
Answer: True
Stability is the mechanism that makes LSD ordering work. After the first pass (ones digit), elements with equal ones digits are in their input order. The second pass (tens digit) sorts by tens digit while preserving ones-digit order for ties, because a stable sort maintains relative order for equal keys. This means each pass adds information rather than discarding the previous pass's work. Without stability, passes would interfere with each other and correctness would be lost.
Question 5 Short Answer
Why does LSD radix sort process digits from least significant to most significant, rather than most to least significant? What would go wrong if you reversed the order?
Think about your answer, then reveal below.
Model answer: Processing least-significant digits first works because the sub-sort is stable: each subsequent pass sorts by a more significant digit while preserving the relative order established by less significant digits. If you reversed the order (MSD first), a later pass sorting by a less significant digit would destroy the ordering of more significant digits, since there's no mechanism to say 'only reorder elements that are tied on the more significant digit.'
The key is that stability lets each pass 'refine' rather than 'restart.' MSD-first radix sort does exist but requires a different structure — typically a recursive approach that partitions into buckets by the most significant digit, then recursively sorts within each bucket. LSD is simpler because a single linear pass of a stable sub-sort is sufficient at each level.