Split in half and conquer

Split it in half

Earlier we said a big task
breaks into small steps.
Here we go one step further.
We take a chunk of a problem
and split it in half.
That half into half again,
and that into half once more.
It becomes smaller and smaller pieces.

Tap a chunk to split it in half. Each tap halves it, until you have small pieces.

Each split
halves what you have to handle.
The big pile felt hopeless,
but one small piece
is far more manageable.
It's the very feeling
of halving a dictionary
to find a word.

The pieces don't overlap

Here's something very important.
The two halves you split
don't overlap with each other.
The left pile and the right pile
don't share the same shirt.
So work done on one side
never has to be done again on the other.
The two are completely separate.

Tap the two pieces to light them up. Not a single part overlaps. Being separate (independent), they can be solved on their own without clashing.

This property of not overlapping,
don't take it lightly.
Because pieces don't overlap,
one side's answer
doesn't spoil the other's.
When you meet problems
where pieces do overlap, the story changes.
That's a different path.

Solve the small piece

If you keep splitting in half,
you reach a tiny piece
that can't be split anymore.
Like a single shirt,
or a single number.
It's so small
that with no fuss
it's solved right away.

Tap a smallest piece (the bottom) to solve it right away. Too small to split further, it's solved with no fuss (green).

We don't strain
to solve the big problem at once.
We split all the way down,
and solve only the small,
easy ones, one by one.
We've turned
a hard task
into many easy ones.

Merge it back up

Now that small answers exist,
we climb back up.
Merge two small answers
into a slightly bigger one,
then merge those two
into a bigger one still.
Merge as much as you split,
and the whole answer stands on top.

Tap the solved pieces to merge them upward. Two into one, then into one again. The whole answer completes at the top.

Going down when we split,
going up when we merge.
Since the pieces didn't overlap,
merging is clean too.
You just line up
the left answer and the right answer.
This, right here,
is splitting in half to conquer.

Split, solve, merge

Gathered in one line, it's this.
Split in half,
solve each non-overlapping piece,
and merge back up.
Halving a dictionary to search,
splitting cards in half to sort
are all this one frame.
Big things shrink when you split them.

Tap the three steps in order to follow one loop. Split in half, solve the small pieces, merge upward. The pieces not overlapping was the key.

Here the pieces sat
cleanly apart from each other.
So a piece solved once
never had to be solved again.
But what if the pieces
overlapped, and you had to keep
re-solving the same thing?
Next lesson, we meet that fork.