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
  1. Count occurrences of each key.
  2. Turn the counts into a prefix sum, so count[v] is the number of elements — the position just past where the s end.
  3. Walk the input backwards, placing each element at count[key]-1 and 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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Sorting