How does divide and conquer work

Split in half

Earlier we said a big task gets broken into small steps. Here we go one step further.
We split the problem in half, split each half in half again, and keep going.
The pieces get smaller and smaller.

Each press splits every piece in half, and the pieces keep getting smaller.

Every split halves the amount you have to deal with.
The big pile felt hopeless, but one small piece is far more manageable.
It's the same feeling as searching a dictionary by halves.

The pieces don't overlap

Here's something very important: the two halves don't overlap.
The left pile and the right pile don't share any clothes, so nothing done on one side has to be done again on the other.
The two are completely separate.

Light up the two pieces one at a time: there's no overlap at all. Because they're separate (independent), solving each on its own causes no clashes.

This no-overlap property matters more than it seems.
Since the pieces don't overlap, the answer on one side can't spoil the answer on the other.
Problems whose pieces do overlap are a different story, and they take a different road.

Solve the small pieces

Keep splitting, and you reach tiny pieces that can't be split any further.
One piece of clothing, one number.
At that size, they're solved right away, with nothing to think about.

Press the smallest pieces (the bottom) one by one to solve them on the spot. They're too small to split, so they're solved without effort and turn green.

We don't struggle to solve the big problem all at once.
We split all the way down, then solve only the easy little pieces, one by one.
We've turned one hard job into many easy ones.

Combine upward

Now that we have small answers, we climb back up.
We combine two small answers into a slightly bigger one, then combine those into a bigger one still.
After as many combines as there were splits, the whole answer stands at the top.

Each press joins the solved pieces two by two. At the top, the whole answer is complete.

Splitting goes down; combining goes up.
Because the pieces didn't overlap, combining is clean too: you just bring the left answer and the right answer together.
This is divide and conquer.

Split, solve, combine

Put in one line: split in half, solve the non-overlapping pieces separately, and combine them back up.
Sorting cards by splitting them in half follows this pattern exactly, and searching a dictionary by halves is the case where you throw away the side without the target, so only one half needs solving.
Big things get small when you split them.

Press the three steps in order to go around once: split in half → solve small pieces → combine upward. The key is that the pieces don't overlap.

Here, the pieces were cleanly separated, so no piece ever had to be solved twice.
But what if the pieces overlapped and the same thing had to be solved again and again?
In the next lesson we'll first look at recursion, where the splitting repeats itself, and right after that we'll reach that fork in the road.