Every time you run a diff ā whether it's git diff in a terminal, a pull request on GitHub, or a text comparison on TextCompareo ā there's an algorithm behind the scenes figuring out the shortest way to get from version A to version B. In most cases, that algorithm is Myers diff.
Published by Eugene Myers in 1986, it's become the de facto standard for text comparison. Git uses it. Most diff tools use it. It's fast, it produces clean results, and it's surprisingly elegant once you understand what it's actually doing.
Here's how it works ā without the academic paper jargon.
What Problem Does Myers Diff Solve?
Given two sequences of text (let's call them A and B), find the minimum number of edits ā insertions and deletions ā needed to transform A into B. That's the "edit distance" problem, and it's trickier than it sounds.
Consider these two strings:
A: ABCABBA
B: CBABACThere are many possible ways to describe the differences. You could say "delete everything and insert the new string" ā that's technically correct but useless. What you actually want is the shortest edit script ā the minimum set of changes that transforms A into B, keeping as much of the original text as possible.
That's what Myers diff finds: the shortest path from one version to the other.
The Edit Graph
Myers' key insight was to represent the problem as a graph. Picture a grid where:
- The x-axis represents string A (the original)
- The y-axis represents string B (the modified version)
- Moving right means deleting a character from A
- Moving down means inserting a character from B
- Moving diagonally (down-right) means the characters match ā no edit needed
The goal is to get from the top-left corner (0,0) to the bottom-right corner (len(A), len(B)) using the fewest right and down moves. Diagonal moves are "free" because matching characters don't count as edits.
So finding the shortest edit script becomes finding the shortest path through this grid ā where "shortest" means fewest non-diagonal moves.
How the Algorithm Works
Myers' algorithm explores the edit graph in waves, starting from the origin:
- Start at (0,0) with zero edits
- Try all paths with exactly 1 edit (one insertion or one deletion), then slide diagonally wherever characters match
- Try all paths with exactly 2 edits, sliding diagonally after each move
- Keep going until you reach the bottom-right corner
The first wave that reaches the destination gives you the shortest edit script. Because it tries fewer edits first (0, then 1, then 2...), the first solution found is guaranteed to be optimal.
The "sliding" along diagonals is what makes this efficient. When two documents are mostly similar (which is the common case), there are long diagonal runs where the text matches. The algorithm blazes through these without counting them as edits.
Why "Shortest" Matters
Why not just flag every difference and call it done? Because the shortest edit script produces the most useful diff.
Consider these two versions:
Original: The cat sat on the mat
Modified: The cat sat on the rugA naive diff might report: "delete 'the mat', insert 'the rug'." But the shortest edit script says: "delete 'mat', insert 'rug'" ā because "the" is shared. The second result is cleaner, easier to read, and tells you exactly what changed.
For code diffs, this matters even more. A clean, minimal diff makes code reviews faster and merge conflicts easier to resolve. That's why Git chose Myers as its default algorithm.
Time Complexity
Myers diff runs in O(ND) time, where N is the total length of both sequences and D is the number of differences. This is important because:
- When documents are similar (small D), it's nearly linear ā very fast
- When documents are completely different (D ā N), it approaches O(NĀ²) ā slower, but still manageable
In practice, most diffs are between similar versions of the same document, so D is small. This makes Myers diff fast for the typical case ā which is exactly why it became the standard.
What You Actually See in the Output
When you use a diff tool, the algorithm's output gets translated into something human-readable:
| Algorithm Output | What You See |
|---|---|
| Delete operation | Red highlighted text (removed from original) |
| Insert operation | Green highlighted text (added in new version) |
| Match (diagonal) | Unchanged text (no highlighting) |
The color-coded output you see in TextCompareo, GitHub, or your terminal is just a visual representation of the edit script that Myers diff computed. Green means "this was inserted," red means "this was deleted," and everything else matched.
Myers Diff vs. Other Algorithms
Myers isn't the only diff algorithm out there, but it's the most widely used for a reason:
| Algorithm | Best For | Trade-off |
|---|---|---|
| Myers diff | General-purpose text comparison | Great balance of speed and output quality |
| Patience diff | Code with moved blocks | Better at matching unique lines, slower overall |
| Histogram diff | Large codebases (Git's alternative) | Faster on some inputs, similar results |
| LCS (Longest Common Subsequence) | Academic/theoretical applications | Equivalent results, less efficient |
For text comparison tools like TextCompareo, Myers is the right choice. It's fast for typical inputs, produces clean minimal diffs, and handles everything from short paragraphs to long documents.
Where You Encounter Myers Diff
Even if you've never heard the name before, you've almost certainly used Myers diff:
- Git ā
git diffuses Myers by default. Every pull request review on GitHub and GitLab runs this algorithm. - Text comparison tools ā many libraries and applications use Myers or a related shortest-edit-script approach; others use patience, histogram, LCS-based, or domain-specific algorithms.
- Code editors ā VS Code, Sublime Text, and JetBrains IDEs use it for inline diff views.
- Merge tools ā Resolving merge conflicts relies on diff output, usually from Myers.
A Simple Example
Let's trace through a small example to make this concrete:
A: A B C
B: A C BThe algorithm starts at (0,0). "A" matches in both strings, so it slides diagonally to (1,1) ā no edit needed.
Now it branches: it can delete "B" (move right) or insert "C" (move down). It tries both paths with 1 edit, extending diagonally wherever possible.
The optimal solution turns out to be: keep "A", delete "B", keep "C", insert "B". That's 2 edits (one deletion, one insertion), and it produces this diff:
A
- B
C
+ BClean, minimal, easy to read. That's Myers diff doing its job.
Frequently Asked Questions
What is the Myers diff algorithm?
It's an algorithm published by Eugene Myers in 1986 that finds the shortest edit script between two text sequences. It identifies the minimum number of insertions and deletions needed to transform one text into another. It's the default algorithm behind git diff and most text comparison tools.
Why does Git use Myers diff?
Because it produces clean, minimal diffs that are easy to read during code reviews, and it's fast for the typical case (comparing similar versions of the same file). Git also offers alternatives like patience diff and histogram diff, but Myers is the default.
What does O(ND) time complexity mean?
N is the total length of both texts, and D is the number of differences. When documents are mostly similar (small D), the algorithm is nearly linear ā very fast. When they're completely different, it gets slower but is still practical.
How is this different from LCS?
LCS (Longest Common Subsequence) and Myers diff are closely related ā finding the shortest edit script is mathematically equivalent to finding the longest common subsequence. Myers' algorithm is just a more efficient way to compute it, especially when the number of differences is small.
Can Myers diff handle non-text data?
The algorithm works on any two sequences, not just text. It can compare lists of numbers, arrays of objects, or any ordered data. But it's most commonly used for line-by-line or word-by-word text comparison.
What is the edit graph?
A grid where one text runs along the x-axis and the other along the y-axis. Moving right means deleting, moving down means inserting, and moving diagonally means the characters match. Finding the shortest diff becomes finding the path through this grid with the fewest non-diagonal moves.
Does TextCompareo use Myers diff?
TextCompareo uses the jsdiff library for line and word comparison. jsdiff documents its implementation as based on Myers' O(ND) difference algorithm, with practical tokenisation and output choices layered on top.
What are the alternatives to Myers diff?
Patience diff (better at matching unique lines in code), histogram diff (faster on some inputs), and various LCS-based approaches. For general text comparison, Myers remains the best balance of speed and output quality.