merge-base: Finding the Common Ancestor

Three-way merge starts with one question: what's the common ancestor? This is the BASE in BASE/OURS/THEIRS. git merge-base A B answers it.

$ git merge-base main feature
4ab38f1da9c2d4e1c2b3a4d5e6f7a8b9c0d1e2f3

Formally: the merge-base of A and B is the lowest common ancestor (LCA) in the commit DAG — a commit reachable from both A and B, such that no other common ancestor descends from it.

Why "lowest"?

Consider:

       a1 (root)
      /  \
     b2   c3
      \   /
       d4 (merge of b2 and c3)
      / \
     e5  f6

merge-base(e5, f6) is d4 — not a1. Both a1 and d4 are common ancestors, but d4 is closer to e5 and f6. Three-way merge against d4 produces a much smaller diff to reconcile.

The algorithm

That's O((N+E)²) — fine for small DAGs, but real git uses paint_down_the_chain with marker bits (each commit gets a bitmask of which sides reached it), which is closer to O(N).

Edge cases

• Linear history: merge-base(A, B) where B descends from A is just A.
• Disjoint roots: two repos grafted together can have no common ancestor — git merge-base exits with status 1 and prints nothing.
• Criss-cross merges (multiple "best" bases) — real git picks one and warns; in this lesson we assume a unique best base.

In practice

Every porcelain command that does a merge calls merge-base first:

• git merge — three-way merge from the base
• git rebase — replay commits since the base
• git cherry-pick — single commit transplant uses base as the patch context

Get this primitive right and most of git's harder commands fall out.