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
  1. To be correct, the algorithm must produce every one of the permutations, so the tree has at least leaves.
  2. A binary tree of height has at most leaves.
  3. 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
BestAvgWorstSpaceStableAdaptive
Bubble1✅✅
Selection1❌❌
Insertion1✅✅

18. Same for the three sorts.

Answer
BestAvgWorstSpaceStable
Merge✅
Quick❌
Heap1❌

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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Sorting