Skip to content
tooljo Diff tools in: Dev tools
100% in your browser. Nothing you paste is uploaded — all processing runs locally. Read more →

How diff algorithms work

9 min read by Samuel Yoo

On this page
  1. The Longest Common Subsequence (LCS) approach
  2. The Myers algorithm
  3. The Patience algorithm
  4. A worked example
  5. Word-level diff
  6. Three-way merge
  7. Practical takeaways
  8. Try the tool
  9. Related across the network

A diff algorithm answers a deceptively simple question: given two sequences, what’s the smallest set of insertions and deletions that turns A into B? “Smallest” is the operative word — multiple correct edit scripts exist for any pair of inputs, and the algorithm that picks the best one is what makes a diff feel right.

Three algorithms power most production diff tools: Longest Common Subsequence (textbook), Myers (Git’s default), and Patience (Bram Cohen’s anti-noise variant). They produce different results for the same input.

The Longest Common Subsequence (LCS) approach

This is the algorithm in textbooks and the one our diff tool uses.

Idea: find the longest sequence of lines that appears (in the same order, not necessarily consecutively) in both A and B. Anything not in that LCS is either a deletion (only in A) or insertion (only in B).

Algorithm (dynamic programming):

dp[i][j] = length of LCS of A[0..i) and B[0..j)

dp[0][*] = dp[*][0] = 0
dp[i][j] =
  dp[i-1][j-1] + 1            if A[i-1] == B[j-1]
  max(dp[i-1][j], dp[i][j-1]) otherwise

After filling the table, walk back from dp[N][M] to extract the actual LCS, then derive the edit script.

Cost: O(N × M) time, O(N × M) memory. Fine for short inputs (a few hundred lines per side) but expensive for thousands of lines.

Output character: picks “any longest” subsequence; can produce non-intuitive alignments when there are repeated similar lines (e.g., multiple } lines in code).

The Myers algorithm

Eugene Myers’ 1986 paper “An O(ND) Difference Algorithm and Its Variations” gave us the algorithm Git, Mercurial, and most modern diff tools use.

Idea: instead of filling the entire LCS table, walk a “frontier” through it. The shortest edit script (SES) of length D only touches O(D) of the table cells per diagonal. So the cost depends on the edit distance, not the input size.

Cost: O((N + M) × D) where D is the edit distance.

Why it’s the default: typical real diffs have small D relative to N + M (you change 10 lines in a 1000-line file, not 500). Myers is proportional to what changed, not the total input size.

Output character: finds an SES, but doesn’t uniquely identify which one — Myers picks the first one it encounters in its diagonal walk. This is where Patience improves on Myers for human readability.

The Patience algorithm

Bram Cohen (BitTorrent) noticed that Myers, while optimal in edit distance, often produces ugly diffs in code: it’ll align a stray } line in A with a } line in B that’s actually unrelated, just because they’re both }. The result: spurious changes scattered across the diff that don’t match how a human would read the change.

Idea: find lines that appear exactly once in both A and B (the “unique” anchor lines). Compute LCS over just those anchors first. Recursively diff the segments between anchors with a fallback (often Myers).

Cost: roughly O(N log N) on top of the recursive sub-diffs.

Why it’s better for code: unique lines tend to be meaningful (function declarations, distinctive comments). Aligning them first avoids the “every closing brace is a candidate” problem.

Where you’ve seen it: Git supports it via --patience. It’s also the default in Bazaar (the version-control system, originally written by the BitTorrent author). Some IDE diff tools use Patience by default.

A worked example

Consider:

A:                  B:
function foo() {    function bar() {
  return 1          // hello
}                     return 1
                    }
function bar() {
  // hello
  return 2
}

LCS might pair: function bar() { (line 4 of A) with function bar() { (line 1 of B), // hello with // hello, return 1 with return 1, } with }. Then it has to delete function foo() {, return 1, }, function bar() {, etc. — a mess.

Myers is similar but slightly cleaner due to its diagonal preference.

Patience identifies function foo() {, function bar() {, and return 2 as unique-in-A; // hello and return 1 as unique-in-B. It pairs the unique function bar() { in both, recurses on the surrounding regions, and produces a much more readable diff: “the foo function was removed, the bar function was renamed/moved.”

Word-level diff

All three algorithms also work at character or word granularity. Most diff tools (including ours) run a second pass at word granularity on lines that were “replaced” — paired delete + insert lines. The output highlights only the substrings that changed, not the entire line.

This is purely a UX improvement; it doesn’t change the line-level edit script.

Three-way merge

When two branches both modified a base file, you need three diffs: A↔base, B↔base, A↔B. The merge algorithm:

  1. Find sections where A and B made the same change → keep that change.
  2. Find sections where one changed and the other didn’t → take the changer.
  3. Find sections where both changed differently → conflict. Mark with <<<<<<<.

Three-way merge is what git merge and git rebase use under the hood. The conflict markers you sometimes see (<<<<<<<, =======, >>>>>>>) are emitted by the merge driver after diff identified a genuine conflict.

The diff viewer on this site is 2-way only; for 3-way you want your editor’s merge tool.

Practical takeaways

Try the tool

The diff viewer on this site uses LCS. Side-by-side and unified views, ignore-whitespace and ignore-case toggles, word-level highlighting on paired changed lines. All in your browser.