Three-Way Merge

The most feared operation in git is a surprisingly small algorithm. Merging isn't magic, isn't AI, and isn't even particularly clever — it's a per-region comparison of three versions with four outcomes, and by the end of this lesson you'll have implemented it and know exactly when it must give up.

Why three, not two?

Try merging with two versions — yours and theirs — and you hit an unanswerable question. Your file has a line theirs lacks: did you add it, or did they delete it? Two-way comparison cannot say; the correct merge differs (keep it vs drop it), so any two-way merger guesses.

The base version answers it — the common ancestor, the snapshot both sides started from (found by walking the commit graph for the last shared commit: the merge-base lesson). Line in base and in yours, missing in theirs → they deleted it → drop it. Line not in base, present in yours → you added it → keep it. History resolves the ambiguity; that's the entire insight, and it's why git commits store parent links at all.

The algorithm

Align the three versions region by region (diff base↔ours and base↔theirs — your diff engine from last lesson is the engine here too), then per region:

Rows two and three do the work: most simultaneous edits in real life touch different regions of a file, so most merges are just the algorithm mechanically picking the changed side, region after region. That's why merges are usually silent — not because git is smart, but because edits rarely collide.

Conflicts are honesty, not failure

The last row is the algorithm reporting a fact: both sides rewrote the same region, and no textual rule can rank human intentions. Git's output is the conflict marker block:

<<<<<<< ours
our version of the region
=======
their version of the region
>>>>>>> theirs

Both candidates, clearly labeled, decision escalated to the only party with authority: you. Note what merging doesn't know — semantics. Both sides compiling, both sides tested, doesn't mean the merged text works (you rename a function, they add a call to the old name: merges cleanly, breaks the build). The textual merge is a floor, not a guarantee — which is why CI runs on merge results.

Your exercise: Three-Way File Merge

Base, ours, theirs in; merged output (with conflict markers where required, in the spec's exact format) out. Route your energy to the boundaries: the pure-addition cases (new line only in ours → keep; check against base, not just theirs!), deletions (changed-to-nothing is still "changed" — the table applies unchanged), both-sides-identical edits (row four — NOT a conflict; implementations that only compare ours-vs-theirs get this right by accident and the deletion cases wrong), and marker format byte-exactness. When it passes, run git merge in any repo and enjoy knowing there's a five-row table where the fear used to be.