Merging & Rebasing

When Git merges two branches, it needs to know where they actually DIVERGED — the merge base (or lowest common ancestor): the most recent commit both branches share. Everything after that point is what each branch actually added independently.

def commit_history(commits, start):
    history = []
    current = start
    while current is not None:
        history.append(current)
        current = commits.get(current)
    return history

def find_merge_base(commits, a, b):
    a_history = set(commit_history(commits, a))
    current = b
    while current is not None:
        if current in a_history:
            return current
        current = commits.get(current)
    return None

Merging creates a new commit with TWO parents, combining both branches' work while preserving exactly what happened (the diverged history stays visible). Rebasing instead REWRITES one branch's commits to sit on top of the other, producing a clean, linear history — as if that work had been done starting from the more recent commit all along.

The tradeoff: merging preserves true history (including exactly when and where branches diverged) at the cost of a messier, more tangled commit graph. Rebasing produces a cleaner, more readable linear history, but LITERALLY rewrites commits (new commit hashes) — which is why the cardinal rule is: never rebase commits that have already been pushed and shared with others, since rewriting shared history breaks everyone else's copy of it.