1. The Intuition: The Split and the Reunion

1.1 The Manuscript Analogy

Imagine two writers, Alice and Bob, who co-author a manuscript. They start with an initial draft (Commit $A$). Alice takes a copy and adds a chapter (Commit $B$). Simultaneously, Bob takes a copy and fixes typos in the preface (Commit $C$). To reunite their work into a final book (Merge Commit $M$), we cannot simply compare Alice's draft ($B$) directly against Bob's draft ($C$). If a paragraph exists in Alice's draft but not in Bob's, did Alice add it, or did Bob delete it? Comparing only their final drafts creates complete ambiguity.

To resolve the ambiguity, we must look at the **Common Base** ($A$) from which they both branched. If a paragraph is present in Alice's draft but missing in the base $A$, we know Alice *added* it. If a paragraph is present in the base $A$ but missing in Bob's draft, we know Bob *deleted* it. This is the core intuition behind three-way merging: we compare three files (Base, Ours, Yours) to compute the correct merge state.

Diagram: The branching commit history forming a DAG where Commit A is the Lowest Common Ancestor.

Pitfall — Blindly running force-push after rebase: Using `git push --force` after resolving merge conflicts or rebasing branches can overwrite commits pushed by teammates in the meantime. Always use `git push --force-with-lease` which aborts the push if the remote branch contains new commits you haven't fetched yet.

2. Three-Way Merge vs Two-Way Merge

2.1 The Two-Way Diff Limitation

A **Two-Way Merge** compares only two files: file $O$ (Ours) and file $Y$ (Yours). If a line differs between the two files, a two-way merge algorithm cannot determine which branch made the modification. This limitation makes automated merging practically impossible, forcing developers to manually resolve every single file difference.

A **Three-Way Merge** introduces a third file: file $B$ (Base), representing the closest shared ancestor of $O$ and $Y$. By comparing $O$ and $Y$ against $B$, Git classifies line changes into four distinct states:

• Unchanged: The line is identical in $B$, $O$, and $Y$. The merged output retains the line.
• Ours Modified: The line changed in $O$ but remains identical to $B$ in $Y$. The merged output adopts the change from $O$.
• Yours Modified: The line changed in $Y$ but remains identical to $B$ in $O$. The merged output adopts the change from $Y$.
• Conflict: The line changed in both $O$ and $Y$ to different values. The merge algorithm pauses and requests developer intervention.

Pitfall — Merging unrelated histories: Running `git merge` on two branches that share no common parent commit fails with the error `fatal: refusing to merge unrelated histories`. This typically happens when initializing a local repository and trying to merge a remote repo with independent commit histories. Bypassing this with `--allow-unrelated-histories` can lead to massive merge conflicts.

3. Locating the Merge Base: Lowest Common Ancestor (LCA)

3.1 Graph Search in the Commit DAG

To execute a three-way merge, Git must identify the **Merge Base** (the Lowest Common Ancestor). Because Git's commit history is stored as a Directed Acyclic Graph (DAG) where nodes are commits and edges point to parent commits, finding the LCA requires walking backward through parent pointers starting from the two branch tips.

The merge base is defined as the closest common ancestor in terms of topological distance. When a commit history is straightforward, a single LCA is located. However, in complex branch topologies (e.g. criss-cross merges), multiple common ancestors can exist simultaneously.

Diagram: A criss-cross merge topology resulting in two distinct common ancestors (X and Y) with no single lowest common ancestor.

3.2 Topological Search and Commit-Graph Binary Indexing

Finding the Lowest Common Ancestor in a commit graph with hundreds of thousands of nodes is a computational challenge. Naive breadth-first searches (BFS) that traverse parent commit references recursively are slow because they require opening and parsing thousands of separate loose object files or packfile indexes on disk.

Modern Git solves this by using the **Commit-Graph** file (`.git/objects/info/commit-graph`), a single binary file that indexes commit relationships, generations, and topological levels. When searching for the merge base, Git loads the commit-graph into memory and runs a modified topological sorting algorithm (Kahn's or Tarjan's algorithm) based on **Generation Numbers**:

The graph traversal walks backward, keeping commit nodes sorted in descending order of generation numbers. By stopping the search when the generation number of active commit nodes drops below the maximum generation number of known common ancestors, Git limits search depth, finding the merge base in less than 10 milliseconds even on repositories with millions of commits.

Pitfall — Resolving criss-cross merges with default strategies: In a criss-cross history, selecting either ancestor `X` or `Y` arbitrarily as the merge base can result in spurious merge conflicts or silent regressions. Git solves this using the Recursive merge strategy, which merges `X` and `Y` into a virtual common ancestor commit first, then uses that virtual commit as the merge base.

4. The Three-Way Merge Diffing Equations

4.1 Mathematical Evaluation Matrix

Let $B$ represent the value of a line in the Base file, $O$ represent the value in Ours, and $Y$ represent the value in Yours. The three-way merge decision function $f(B, O, Y)$ is defined by the following mathematical mapping:

This mathematical matrix guarantees that if only one side modified the line, that modification is automatically accepted. A conflict is triggered *only* when the line differs on both sides and neither matches the shared base.

4.2 Pre-requisite: Myers Diff and Longest Common Subsequence

Before Git can apply the three-way merge decision matrix, it must align the files line-by-line. It does this by running the **Myers Diff Algorithm** (an $O(ND)$ time complexity shortest-path search in an edit graph) or calculating the **Longest Common Subsequence (LCS)** matrix between the files:

By mapping files to their LCS, Git groups the code into unchanged blocks, deleted sequences, and inserted blocks. The three-way merge matrix is then evaluated strictly on the aligned blocks, preventing misaligned diff lines from corrupting the merge output.

5. How Merge Conflicts Occur & How Git Marks Them

5.1 Conflict Markers and Git Index Stages

When the merge engine encounters a conflict state, it does not write a final commit. Instead, it writes **conflict markers** directly into the working directory files and updates the **Git Index** (staging area) with three distinct versions of the conflicting file:

• Stage 1 (Ancestor): The file version from the merge base ($B$).
• Stage 2 (Ours): The file version from your current branch ($O$).
• Stage 3 (Yours): The file version from the branch being merged ($Y$).

Pitfall — Forgetting to clear stage 1/2/3 index files: When resolving conflicts manually, simply editing the file text does not fully notify Git. The file remains locked in stages 1, 2, and 3 inside the index. You must run `git add ` to collapse the three staging versions back into a single clean Stage 0 entry, allowing `git commit` to proceed.

6. Fast-Forward vs Merge Commits

6.1 Fast-Forward Merges

A **Fast-Forward (FF)** merge occurs when the target branch tip is a direct descendant of the current branch tip. Because no divergent commit history exists, Git does not execute a three-way merge. Instead, it simply moves the current branch pointer forward to point to the target branch commit. No new merge commit is created.

If the histories have diverged (both branches contain unique commits since the split), a fast-forward is mathematically impossible. Git is forced to perform a three-way merge, creating a new **Merge Commit** featuring two parent references. The divergence relation can be expressed as:

6.2 Preserving History context via --no-ff

Even when a fast-forward merge is possible, teams often configure Git to force a merge commit using `git merge --no-ff feature`. Without `--no-ff`, fast-forwarding leaves no record of the feature branch's existence; its commits blend directly into the main timeline. Forcing a merge commit creates a permanent visual grouping in the DAG, showing exactly when a feature was integrated.

Pitfall — Rebase-and-merge flattening commits: While rebasing a feature branch and fast-forwarding it onto main keeps history strictly linear, it destroys parent link records. If a feature contains experimental or broken steps, rebasing flat makes it extremely difficult to identify and revert the entire feature unit in production using a single `git revert` command. Use merge commits for complete features.

7. Advanced: C-Git's ORT (Ours, Recursive, Three-way) Merge Strategy

7.1 The Modern Merge Engine

For over a decade, Git's default merge engine was the `recursive` strategy. In Git 2.34, it was replaced by **ORT (Ours, Recursive, Three-way)**. Written in pure C, ORT was designed to address performance limitations in large monorepos. ORT optimizes merges through:

• Rename Detection Caching: Renaming files during a merge requires $O(N \times M)$ directory comparisons. ORT caches rename candidates, reducing merge times by up to $100\times$ on large refactors.
• Conflict Resolution Deferral: Avoids writing partial states to the disk staging area until all file conflicts are computed, preventing expensive I/O operations.
• Virtual Ancestor Synthesis: Automatically creates temporary virtual merge commits in memory when resolving multiple merge bases in criss-cross branches.

7.2 Under the Hood of ORT Rename Detection

During large refactors, files are often moved across directories while simultaneously being edited on another branch. C-Git's ORT strategy detects renames using similarity index algorithms based on the Levenshtein distance or hashing algorithms comparing block similarity. Once ORT detects that `/src/old.java` in the Base commit matches `/src/new.java` in Yours with a similarity score $S \ge 50\%$, it maps Ours changes made to `/src/old.java` directly onto the new file location `/src/new.java` automatically.

ORT caches these similarity computations across the entire merge session. If a criss-cross merge contains multiple merge bases, ORT only calculates similarity mappings once and reuses them during the virtual ancestor synthesis steps, eliminating redundant CPU-heavy diff operations.

Pitfall — Lowering rename detection thresholds too far: Configuring `git config merge.renameLimit` to extremely high values or setting `merge.renames` to search for very low similarity percentages (e.g. $<30\%$) forces Git to run expensive pairwise file diffs, freezing the CPU for minutes on large monorepos. Keep the default threshold at $50\%$ similarity.

8. Advanced: Staging Area Internals During Conflict

8.1 Staged File Inspection

When a merge conflict halts, you can inspect the raw files stored in the Git Index stages using `git ls-files -u`:

Using `git show :1:src/App.java` prints the raw contents of the common base version, allowing tools to perform three-way visual comparisons directly from memory without writing temporary files to the disk.

8.2 Programmatic Conflict Resolution via Checkout

When automatic merge conflict resolution is needed in CI/CD pipelines or scripts, you can programmatically bypass manual editing of conflict markers. To resolve conflicts by choosing one branch entirely, use the staging checkout commands:

These checkout commands write the exact blob reference from Stage 2 or Stage 3 directly into the working directory file. Running `git add` afterwards updates the index, clearing Stage 1, 2, and 3 entries and placing the chosen blob reference at Stage 0, signaling Git that the conflict is fully resolved.

9. Git Integration Strategy Comparison

The table below compares common Git strategies for integrating changes across branches:

10. Interactive: Three-Way Merge Simulator

Click "Merge Branches" to run the Lowest Common Ancestor (LCA) search and execute a three-way merge simulation on the commit DAG:

11. Merge Strategy Performance Comparison

The chart below compares execution times (in milliseconds) of different merge engines on a repository containing 10,000 files with rename detection active:

12. Frequently Asked Questions