How Diff Algorithms Power Version Control

Every time you run git diff, review a pull request, or use a text-comparison tool to see what changed between two versions of a file, there's an algorithm quietly solving a surprisingly subtle problem: given two sequences of lines, what is the smallest possible set of insertions and deletions that turns one into the other? That problem is harder than it sounds, and the most widely used solution — the Myers diff algorithm, published by Eugene Myers in 1986 — is worth understanding, because it explains both why diffs sometimes look "weird" and why they're so fast even on huge files.

Why this isn't as simple as "line by line"

A naive approach might compare files line by line: if line 5 in the old file doesn't match line 5 in the new file, mark it changed. This falls apart immediately the moment a single line is inserted or deleted anywhere before the end of the file — every subsequent line shifts by one position, and a line-by-line comparison would report every remaining line as "changed" even though only one line actually differs. What you actually want is something closer to alignment: find which lines in the old file correspond to which lines in the new file (even if their positions shifted), and report only the lines that don't have a correspondence at all.

Reframing it as a graph problem

Myers' key insight was to reframe the diff problem geometrically. Picture a grid where moving right represents "delete a line from the old file" and moving down represents "insert a line from the new file." Diagonal moves are free — they represent a line that exists, unchanged, in both files. Finding the smallest diff becomes equivalent to finding the shortest path from the top-left corner of this grid to the bottom-right corner, where the path is allowed to move diagonally for free whenever the corresponding lines match, and costs one step for every horizontal or vertical move (an insertion or deletion). This is the "edit graph," and the length of the shortest path through it is called the edit distance — the minimum number of insertions and deletions needed to turn one sequence into the other.

This reframing matters because shortest-path problems on grids are well understood, and Myers showed that this particular shortest-path problem can be solved in O(ND) time, where N is the combined length of both sequences and D is the size of the edit script (the number of actual insertions and deletions). Crucially, D is usually small relative to N for real-world diffs — two versions of a source file that differ by a handful of lines have a small D even if the files themselves are thousands of lines long — which is why diffing even large files feels instant in practice.

The linear-space refinement

The original O(ND) algorithm as described uses O(ND) space too, which becomes a real problem for very large inputs — a diff between two huge generated files, for instance. Myers also described a divide-and-conquer refinement that finds the diff using only O(N) space, by finding a single "middle snake" (a point the optimal path must pass through) using a forward-and-backward search from both ends of the sequences simultaneously, then recursively solving the two halves on either side of that midpoint. This is the version most production diff tools actually implement once inputs get large, since it trades a small amount of additional computation for a much better memory profile — the difference between a diff tool that handles a 100,000-line file gracefully and one that runs out of memory trying.

Why diffs sometimes look "wrong"

A minimal edit script isn't always the one a human would intuitively pick. If a block of code is deleted from one place and an identical block is added somewhere else, a diff algorithm focused purely on minimizing edit count might represent this as a scattered set of small insertions and deletions rather than one clean "moved block," because the algorithm has no concept of "moving" — only inserting and deleting. This is also why diffing algorithms are often paired with heuristics for things like "prefer to align diffs on blank lines" or "prefer whole-line changes to overlapping partial-line changes" — these don't change the mathematical minimum, but they nudge the algorithm toward the specific minimal solution that tends to read more naturally to a human, among the (often many) edit scripts that are all equally minimal in length.

Word-level vs. line-level diffing

The same underlying algorithm works regardless of what you treat as the atomic unit being compared — it doesn't have to be a line. Tokenizing by word instead of by line and running the same edit-distance search produces a word-level diff, which is far more useful for prose or for a single long line of minified code where line-level diffing would just report "this entire line changed" even if only one word did. The trade-off is computational: word-level tokenization produces a much longer sequence for the same input, so it's more expensive, which is why practical tools often default to line-level diffing for large inputs and offer word-level as an opt-in for when the extra precision is worth the cost.

Why it matters beyond version control

The exact same core problem — and often the exact same algorithm — shows up anywhere two versions of structured data need to be compared: diffing two JSON documents to see what changed in an API response, comparing two configuration files, or generating a patch file. Once you see the edit-graph framing, "diff" stops looking like a special-purpose text tool trick and starts looking like what it actually is: a general shortest-path problem that happens to have an unusually elegant solution.