Algorithm comparison
Git has more than one way of producing a diff. All of them are correct; what differs is which answer a human finds easiest to read. This page runs all of them at once so the difference is visible.
Myers, patience, and histogram on the same input. Patience usually produces a longer script — that is the point: minimal is not the same as readable.
Give it two texts
Old version on the left, new version on the right. Nothing to hand? Take one from the presets.
Before anything is compared the text becomes a list of numbers — one per line, word or character. That choice is what counts as being the same, so it changes the grid, the D, and the diff that comes out. A diff is not one thing: it is the answer to the question you asked.
The numbers
| Algorithm | Script length (D) | Hunk count | V cells stored | Guarantees minimal |
|---|---|---|---|---|
| Myers | 2 | 1 | 16 | Yes |
| Myers — linear space | 2 | 1 | 22 | Yes |
| Patience | 2 | 1 | — | Not guaranteed |
| Histogram | 2 | 1 | — | Not guaranteed |
- Script length (D)
- Lines deleted plus lines inserted. Smaller is tighter.
- Hunk count
- How many separate chunks you have to read. Fewer is usually kinder.
- Guarantees minimal
- Whether the algorithm guarantees the smallest possible D — not whether its D happens to be minimal on this input.
The linear-space variant stored more cells than greedy here. That is not a miscount: it trades O(D²) storage for O(N+M) plus a fixed recursion overhead, and on an input this small the overhead wins. The order reverses as D grows — open a larger preset in the edit graph to watch it.
On this input all four agree: same D, same number of hunks. That is the common case on small edits — the differences appear when a repeated line gives Myers somewhere else to anchor. Try the "Where patience wins" preset.
Only Myers guarantees a minimal D. Patience and histogram trade minimality for readability.
The output, side by side
One input, four ways of reading it.
Myers
D = 2 · 1 hunk
Myers — linear space
D = 2 · 1 hunk
Patience
D = 2 · 1 hunk
Histogram
D = 2 · 1 hunk