Five tasks.

---

1. Where stability goes

Change the Merge condition from a[i].Title <= b[j].Title to <.

Run dcsort_test.go. Which test fails? And did the algo dc numbers change? Explain why one character changes neither the complexity nor the comparison count, but does change the result.

---

2. Why median-of-three is not enough for reverse order

Step 7 showed median-of-three staying quadratic on reverse-sorted input.

Find the reason. Log the p returned by every Partition and look at how the slice divides over the first ten levels. Is the first split good? What about the second?

(Hint: the first split is perfect. The problem is in what Partition leaves behind.)

---

3. Hoare partitioning

Implement PartitionHoare — the two-pointer scheme, walking from both ends towards each other.

Run median-of-three with it on reverse-sorted input. Did the quadratic behaviour go away? If so, your answer to task 2 is confirmed.

---

4. Three-way partitioning

Generate a library with -dup-rate 0.9: ten percent distinct titles, the rest repeats.

Run all four algorithms. Which suffers most, and why?

Then implement a three-way split (less / equal / greater) and measure again.

---

5. Recursion depth

QuickSortNaive on sorted input recurses n levels deep.

In lesson 5 you measured Go's stack as holding about 8 million frames. How large would a sorted slice have to be to break QuickSortNaive?

Work it out, then check. And consider why sort.Slice never does this — the answer is limit := bits.Len(uint(length)) in its code.