Micro-questions over the lower bound module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Why six algorithms
1. Sorting is solved. Why does it need six algorithms?
Answer
Because “sorted” is not the only requirement — you may need stability, no spare memory, adaptivity on almost-sorted input, or keys of a special kind. The constraints conflict, so there is no single winner.
2. What rare kind of result does this lesson contain?
Answer
A proof about every possible algorithm, not just the ones we have thought of.
B. The vocabulary
3. What is a comparison sort?
Answer
One that decides order only by comparing pairs. It is the kind the lower bound applies to.
4. What does stable mean?
Answer
Equal elements keep their original relative order.
5. Give the concrete reason stability matters.
Answer
Sort employees by name, then by department. If the second sort is stable, people stay alphabetical within each department. If it is not, the first sort was wasted.
6. Which standard library sorts are stable?
Answer
Python’s sorted() and Java’s Arrays.sort for objects. It is the single most-overlooked property.
7. What does in-place mean here?
Answer
Uses or extra space. It matters when data barely fits.
8. What does adaptive mean, and why does it matter?
Answer
Faster on partly-sorted input — and real data is often partly sorted.
9. Internal versus external?
Answer
Fits in memory versus does not. External sorting is a different problem.
C. The proof
10. State the claim.
Answer
Any comparison-based sorting algorithm needs comparisons in the worst case.
11. What is a decision tree here?
Answer
Each internal node is one comparison, with two branches for the two outcomes; each leaf is a final ordering the algorithm can output.
12. Give the three steps of the proof.
Answer
- To be correct, the algorithm must produce every one of the permutations, so the tree has at least leaves.
- A binary tree of height has at most leaves.
- So , giving .
13. Finish it.
Answer
By Stirling’s approximation, . And is the worst-case number of comparisons — the longest root-to-leaf path.
14. What did the proof not assume?
Answer
Nothing about the strategy, the data structure, or the cleverness. It applies to every comparison sort that exists or ever will.
15. How close is merge sort to the bound?
Answer
Essentially optimal — its actual comparison count tracks closely.
16. Counting sort runs in , beating . Does that disprove the theorem?
Answer
No. Counting sort is not a comparison sort — it reads the keys themselves rather than comparing pairs, so the bound does not apply to it.
D. The map
17. Give best/average/worst, space, stable and adaptive for the three elementary sorts.
Answer
| Best | Avg | Worst | Space | Stable | Adaptive | |
|---|---|---|---|---|---|---|
| Bubble | 1 | ✅ | ✅ | |||
| Selection | 1 | ❌ | ❌ | |||
| Insertion | 1 | ✅ | ✅ |
18. Same for the three sorts.
Answer
| Best | Avg | Worst | Space | Stable | |
|---|---|---|---|---|---|
| Merge | ✅ | ||||
| Quick | ❌ | ||||
| Heap | 1 | ❌ |
19. Same for the non-comparison sorts.
Answer
Counting: throughout, space , stable. Radix: throughout, space , stable.
20. Why is selection sort even in the best case?
Answer
It always scans the whole remaining array to find the minimum, regardless of how sorted the input already is. It has no early exit to take.
E. What real libraries do
21. What is Timsort?
Answer
Python’s sort — merge sort exploiting existing runs, falling back to insertion sort on small pieces. Stable and adaptive.
22. What is introsort?
Answer
C++‘s std::sort — quicksort, switching to heapsort when recursion goes too deep, so the worst case cannot happen.
23. Why do both hybrids exist?
Answer
For the same two reasons: insertion sort has the smallest constant on tiny inputs, and quicksort’s worst case must be prevented rather than hoped against.
F. Traps
24. Is quicksort always fastest?
Answer
It has the best constants in practice and an worst case. Library implementations guard against it rather than trusting it.
25. Why is not automatically “fast enough”?
Answer
For it is comparisons. Sorting is often the thing to avoid — via a hash map or a heap.
26. You need the th largest element. What should you not do?
Answer
Sort first. That is ; quickselect is and a heap is . Finding the plain maximum is .
27. Summarise the lesson in one sentence.
Answer
Comparison sorting cannot beat because it must distinguish outcomes with binary questions — and everything else about choosing a sort is stability, space and adaptivity, not speed.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- The Lower Bound — the module
- Elementary Sorts — Question Bank
- Non-Comparison Sorts — Question Bank — what escapes the bound
Software engineering
Infrastructure & security
Computer science
Hardware & engineering