How to Learn Myers’ Diff Algorithm: Edit Graphs, D-Paths, Shortest Edit Scripts and Linear-Space Reconstruction

Quick Read. Myers’ diff algorithm explains how tools can compare two sequences and find a short sequence of insertions and deletions that turns one into the other. The beginner should first draw the edit grid and understand what a diagonal match means. The intermediate learner should trace the furthest-reaching point on each diagonal for edit distance D. The advanced learner should connect shortest edit scripts to longest common subsequences and understand the O(ND) analysis. The professional should learn linear-space reconstruction, readable-diff heuristics, pathological inputs and the difference between mathematical minimality and a diff that humans can review.

One-sentence answer

Myers’ algorithm searches an edit graph by increasing numbers of insertions and deletions, keeping only the furthest point reached on each diagonal, so sequences that differ by a small edit distance can be compared much faster than filling the entire dynamic-programming table.

Why this algorithm exists

Suppose two versions of a program contain thousands of lines but only twelve meaningful changes. A full longest-common-subsequence dynamic programme can spend work proportional to the product of the sequence lengths even though the answer is small. Diff tools need a method whose effort tracks how different the inputs actually are.

Eugene Myers reframed the problem as a shortest path through an edit graph. That move is the conceptual breakthrough. Instead of thinking first about a table of subproblems, think about a path whose horizontal and vertical moves are edits and whose diagonal moves consume equal elements for free.

Level 1 — Beginner: build the edit graph

Let A have length N and B have length M. Put A along the horizontal axis and B along the vertical axis. A horizontal move means delete one element from A. A vertical move means insert one element from B. When A[x] equals B[y], a diagonal move advances through both sequences at zero edit cost.

Right: delete from A.
Down: insert from B.
Diagonal: keep a matching element.

A path from (0,0) to (N,M) therefore describes an edit script. The shortest path measured only in horizontal and vertical moves gives the smallest number of insertions plus deletions. This quantity is often written D.

Start with tiny strings. For A = ABC and B = ADC, the path keeps A, replaces B with D by one deletion plus one insertion, then keeps C. Draw this before touching code. The geometry makes the later recurrence much easier to reconstruct.

The diagonal coordinate k

Every grid point lies on a diagonal identified by k = x − y. A deletion increases k by one; an insertion decreases k by one; matching diagonals keep k unchanged. After exactly D edits, only diagonals whose parity agrees with D are reachable.

Myers’ key compression is to store, for each reachable diagonal k, only the largest x-coordinate reached so far. If two paths arrive on the same diagonal using the same number of edits, the path that is farther to the right dominates the other because it has consumed at least as much of both inputs.

Level 2 — Intermediate: furthest-reaching D-paths

V[1] = 0
for D = 0,1,2,...:
    for k = -D, -D+2, ..., D:
        choose insertion or deletion predecessor
        x = furthest x reachable on diagonal k
        y = x - k
        while x < N and y < M and A[x] == B[y]:
            x += 1
            y += 1
        V[k] = x
        if x == N and y == M:
            return D

The inner while-loop follows what Myers calls a snake: a maximal run of matching diagonal edges after one edit. The algorithm always extends a candidate through every free match before storing its furthest reach.

The decision between predecessor diagonals can be understood geometrically. From k−1 we arrive by deleting from A. From k+1 we arrive by inserting from B. Choose whichever gives the larger x after the edit, then take the snake.

A trace worth doing by hand

Take two short sequences such as ABCABBA and CBABAC. Make a table with D down the left and k across the top. For each D, record the furthest x reached on every legal diagonal. Do not write code until you can explain why one stored coordinate makes every weaker coordinate on the same diagonal irrelevant.

This trace teaches the real algorithm. Memorising the array update without seeing the dominance relation usually produces off-by-one errors and weak understanding.

Why O(ND) appears

At edit distance D, there are O(D) reachable diagonals. Across D = 0 through the final edit distance, there are O(D²) diagonal updates, but the diagonal snakes collectively account for additional sequence scanning. Myers’ original analysis gives O(ND) time for the basic algorithm, where N is the combined input scale and D is the length of a shortest edit script. When D is small compared with the input, this is exactly the regime diff tools care about.

The important comparison is not “O(ND) versus O(NM) in the abstract.” It is: what does D look like in the workload? Version-control files often have long common regions separated by relatively few edits, making an output-sensitive style of reasoning valuable.

Shortest edit script and longest common subsequence

If the allowed edits are insertions and deletions, every element that survives corresponds to a common subsequence. Let L be the length of a longest common subsequence. Then a shortest edit script has length D = N + M − 2L. This relationship links Myers’ path view to the classic LCS problem.

This is also a useful correctness bridge. A shortest path through the edit graph maximises the number of zero-cost diagonal matches, and those diagonal matches form a common subsequence.

Level 3 — Advanced: reconstruct the actual diff

Finding D is not enough; a diff tool must recover the edits. The straightforward approach stores the V array for every D and then walks backward through those snapshots. This is simple to teach but can use substantial memory.

The linear-space variation uses a divide-and-conquer strategy. Search forward from the beginning and backward from the end until the frontiers overlap. That identifies a middle snake. Recurse on the subproblems before and after that snake. The result reconstructs a shortest edit script while keeping memory proportional to the input lengths rather than the area of the full edit grid.

Minimal is not always readable

A shortest edit script is mathematically clean, but humans review source code rather than abstract sequences. Several equally short scripts may exist, and one may align braces, blank lines or repeated statements in an awkward way. Modern version-control systems therefore combine core diff algorithms with heuristics that improve hunk boundaries or offer alternatives such as patience and histogram diff.

Current Git documentation still exposes myers, minimal, patience and histogram as explicit diff-algorithm choices. That is a professional lesson: the optimisation objective “fewest edits” and the human objective “most understandable patch” are related but not identical.

Professional implementation decisions

Define the token. Are you diffing bytes, Unicode code points, words, lines, syntax nodes or records?
Trim common prefixes and suffixes. Large identical ends can be removed before the expensive core.
Choose reconstruction strategy. Snapshotting V is simpler; bidirectional middle-snake reconstruction saves memory.
Handle repeated material. Files full of identical braces or blank lines can produce visually poor but minimal alignments.
Separate optimality from presentation. Hunk shifting, move detection and syntax-aware grouping belong to a layer above the edit-path search.
Protect against memory spikes. Very different large inputs can drive D upward.

Failure cases to test

Two identical sequences: D = 0.
One empty sequence.
Completely different sequences.
One insertion at the beginning, middle and end.
Long repeated runs with many equivalent alignments.
Alternating patterns such as ABABAB versus BABABA.
Large common prefix and suffix with a tiny middle edit.
Random small inputs checked against a full dynamic-programming LCS oracle.

The slow oracle matters. For small cases, compare the edit length and reconstructed script against a simple O(NM) implementation. Differential testing is one of the safest ways to find diagonal-index and reconstruction bugs.

Common misconceptions

“Diff means Levenshtein distance.” Myers’ classic formulation minimises insertions plus deletions; substitution is represented as a delete-and-insert pair.
“The algorithm stores the whole grid.” Its central trick is that it does not.
“A diagonal step costs one.” A diagonal is a zero-cost match.
“Shortest diff means best code review.” Readability may require heuristics beyond edit minimality.
“O(ND) is always fast.” When D approaches the input size, the advantage can shrink sharply.

A learning route from beginner to professional

Beginner: draw the edit graph for five-element sequences and label insertion, deletion and match moves.
Intermediate: trace V[k] for successive D values and explain the dominance invariant.
Advanced: prove the LCS relationship and implement shortest-edit-length plus backtracking.
Algorithm engineer: implement the linear-space middle-snake version and differential-test it.
Professional: compare Myers, minimal, patience and histogram output on real repositories and separate algorithmic optimality from review ergonomics.

For teaching, a Predict–Run–Investigate–Modify–Make sequence works well: predict the next furthest diagonal, run the hand trace, investigate why only the maximum x matters, modify one symbol and observe how D changes, then implement. Faded worked examples and Parsons-style ordering tasks are useful while learners are still constructing the edit-graph mental model because they reduce syntax load without removing algorithmic reasoning.

Authoritative sources and further reading

E. W. Myers, An O(ND) Difference Algorithm and Its Variations, Algorithmica 1, 1986.
Git diff-algorithm documentation, current documentation for Myers, minimal, patience and histogram choices.
Git diff documentation, including diff heuristics and algorithm-selection behaviour.
S. Sentance, J. Waite and M. Kallia, Teachers’ Experiences of Using PRIMM to Teach Programming in School, SIGCSE 2019.
L. E. Margulieux, B. B. Morrison and A. Decker, Reducing Withdrawal and Failure Rates in Introductory Programming with Subgoal-Labeled Worked Examples, International Journal of STEM Education, 2020.
C. Szabo et al., Parsons Problems and Computing Education Learning Theories, Koli Calling 2025.

Closing idea. Myers’ algorithm is a lesson in representation. Once comparison becomes a path problem, the algorithm can ignore most of the grid and remember only the frontier that still has a chance to win.