Diff Algorithms Explained: Myers, Patience, and Histogram

Given two sequences of lines — call them A and B — a diff algorithm finds the shortest sequence of insertions and deletions that transforms A into B. This is formally called the Edit Distance or Longest Common Subsequence (LCS) problem.

The naive solution is to check every possible combination of insertions and deletions, but that is computationally explosive for real files. Practical diff algorithms find an optimal or near-optimal edit script efficiently. The three most widely used are the Myers algorithm, the Patience algorithm, and the Histogram algorithm.

The Myers algorithm, published by Eugene W. Myers in 1986, finds the minimum edit script — the smallest possible number of insertions and deletions to transform A into B. It is the default algorithm in git diff, GNU diff, and most diff tools.

Myers works by searching through an "edit graph" — a grid where moving right means taking a line from A, moving down means taking a line from B, and moving diagonally means the lines match. Finding the shortest path from the top-left to the bottom-right of this grid is equivalent to finding the minimum edit. Myers uses a clever diagonal-band search that runs in O(ND) time, where N is the total number of lines and D is the size of the edit.

Myers produces the mathematically optimal diff, but "optimal" does not always mean "most readable." When multiple edit scripts have the same minimum length, Myers picks one — but it might not be the one a human would have written.

The Patience algorithm, popularised by Bram Cohen (creator of BitTorrent), takes a different approach. Instead of minimising total edits, it anchors the diff on unique lines — lines that appear exactly once in A and exactly once in B.

The algorithm finds these unique matching lines first, treats them as fixed anchors, and then recursively diffs the blocks between them. This produces diffs that tend to align on meaningful structural boundaries — function definitions, class declarations, closing braces — rather than on arbitrary matching lines.

The result is a diff that is often easier for a human to read, even if it is not technically the minimum edit. Patience diff is the default in Bazaar and is available in git diff --diff-algorithm=patience. It shines on code that has been significantly refactored — where Myers might produce a confusing tangle of small edits, Patience produces a clean "this block moved here" view.

The Histogram algorithm is an evolution of Patience diff developed for the JGit project (Java implementation of Git). It works similarly — anchoring on low-frequency lines — but instead of requiring lines to be unique, it ranks lines by how frequently they appear and prefers to anchor on rarer lines.

This makes Histogram more robust than Patience in situations where there are no truly unique lines — for example, a file full of similar boilerplate or a config file with many repeated keys. Where Patience would fall back to Myers when no unique lines exist, Histogram still finds good anchoring points by picking the least-common lines.

git diff --diff-algorithm=histogram is the algorithm used by GitHub's diff viewer. It is generally considered to produce the best human-readable results for source code, particularly for files with repeated patterns.

FreeDiffChecker's text diff uses a Myers-based implementation for its core line-level diff, with post-processing to pair similar removed and added lines for word-level and character-level highlighting. This is what the Smart, Word, and Char precision modes control — not the underlying edit-distance algorithm, but how the word-level highlighting is computed within changed line pairs.

For most diffs — comparing two versions of a document, checking API responses, reviewing a patch — Myers is perfectly adequate. For complex code refactors where readability matters, running git diff --diff-algorithm=histogram in your terminal will often give you a cleaner view than any online tool.

For everyday file comparison and document diffing, the algorithm choice is invisible — any modern tool will give you the same result. Algorithm choice matters most when diffing heavily restructured code, where Histogram or Patience diffs align better with how a human would describe the change. For those cases, use git diff with an explicit algorithm flag rather than an online tool. Use online tools for everything else.