Micro-questions over the non-comparison sorts module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Escaping the bound
1. These sort in despite the lower bound. Why is there no contradiction?
Answer
They never compare two elements.
2. What do they use instead?
Answer
The key itself as information — as an array index, or as a sequence of digits.
3. State the difference in terms of the question asked.
Answer
The decision-tree model assumes the only question you may ask is “is ?”. These ask “what is the value of ?”
4. What is the cost of that extra power?
Answer
A loss of generality. A comparison sort works on anything with an ordering — strings, tuples, custom objects, user comparators. These need small non-negative integer keys, or keys decomposable into digits.
B. Counting sort
5. Give the three steps.
Answer
- Count occurrences of each key.
- Turn the counts into a prefix sum, so
count[v]is the number of elements — the position just past where the s end. - Walk the input backwards, placing each element at
count[key]-1and decrementing.
6. What is the cost?
Answer
time and space, for keys in .
7. When is it worth it?
Answer
When is . A million ages () is superb; a thousand 64-bit integers means and an impossible array.
8. Why walk backwards?
Answer
That is what makes it stable. Going backwards places later-occurring equal elements at higher positions, preserving their original order. Forwards, they come out reversed.
9. Why does that stability matter far more than it looks?
Answer
Because radix sort depends on it.
C. Radix sort
10. What problem does radix sort fix?
Answer
Counting sort is useless for large key ranges. Radix sorts one digit at a time, so is only the digit base (10, or 256), never the full key range.
11. What is the cost?
Answer
for digits in base — linear in when is fixed.
12. What does the whole thing rest on?
Answer
Stability. When sorting by the tens digit, two numbers with the same tens digit must stay in the order the units pass left them.
13. What happens with an unstable inner sort?
Answer
It destroys the previous pass’s work and the final result is simply wrong — silently. This is the single most important dependency in the algorithm.
14. Would most-significant-digit-first work just as well?
Answer
Not in the same way. MSD splits into buckets by the top digit, and those buckets must then be sorted independently and recursively. That works — it is what you use for variable-length strings — but it is a different, more complex algorithm.
15. Why does LSD work as a flat sequence of passes?
Answer
Because each pass builds on the last — stability carries the previous passes’ ordering forward as a tiebreak.
D. Bucket sort
16. Describe it.
Answer
Distribute into buckets by value range, sort each bucket (usually with insertion sort), concatenate.
17. What is its cost, and under what assumption?
Answer
Average when the input is uniformly distributed over the range.
18. How load-bearing is that assumption?
Answer
Completely. If everything lands in one bucket you have done a distribution pass and then an insertion sort. Bucket sort is the least robust of the three and the most dependent on knowing your data.
E. Traps
19. How do you handle negative numbers?
Answer
Counting sort indexes an array by key, so negatives need an offset. Radix needs explicit sign handling too.
20. Can you use a custom comparator with these?
Answer
No. They need integer keys or digit decompositions — there is no comparison for a comparator to define.
21. When does walking forwards in counting sort actually break something?
Answer
Usually it does not matter — until you use it inside radix sort, where it breaks correctness.
22. Summarise the three in one sentence.
Answer
Read the key instead of comparing it — counting sort when the range is small, radix sort when it is not (on a stable inner sort), and bucket sort only when you know the distribution is uniform.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Non-Comparison Sorts — the module
- The Lower Bound — Question Bank — the theorem these sidestep
Software engineering
Infrastructure & security
Computer science
Hardware & engineering