Divide and Conquer as a Design Method
Split the input, solve the pieces the same way, and spend the remaining effort combining. Seen as a method rather than as one sorting trick, it produces fast multiplication, closest-pair search, and selection without sorting.
What a learner can do afterwards
- Design a divide and conquer solution to a problem the learner has not seen solved that way
- Say where the work sits for a given split: mostly in the split, the combine, or the leaves
- Explain why splitting into pieces of unequal size can still pay off
1 · Read
Divide and conquer is a design method with three moves. Split the input into smaller pieces, solve each piece the same way, then combine the answers. The recursion stops on pieces so small you solve them directly. Split into two, split every piece again, and you hold four pieces.
Selection without sorting shows the shape. Split the input, keep only the piece that holds the answer, and solve that piece the same way. The skipped piece is work you never do.
For any split, ask where the work sits. It can sit mostly in the split, mostly in the combine, or down in the leaves. If splitting is free and combining scans the pieces, the combine dominates.
Unequal pieces can still pay off. If one piece holds almost all the input, you still shrink the problem every round. Judge a split by its total cost, not by its symmetry.
Split the input, solve the pieces the same way, combine the answers, and judge each split by where the work sits.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.