Diff algorithms are among the most important yet underappreciated algorithms in software engineering, forming the backbone of version control systems, collaborative editing, and any system that tracks changes between document versions.

The foundational algorithm for computing differences is based on the Longest Common Subsequence (LCS) problem, which finds the longest sequence of elements common to both inputs while preserving order. The classic dynamic programming solution to LCS runs in O(n*m) time and space, where n and m are the lengths of the two sequences. In 1986, Eugene Myers published "An O(ND) Difference Algorithm and Its Variations," which computes the shortest edit script (minimum number of insertions and deletions) in O(ND) time, where D is the number of differences. This algorithm is the foundation of GNU diff and Git's default diff engine. For files that are mostly similar — the common case in version control — Myers' algorithm is nearly linear, making it practical for real-world use.

Beyond Myers' algorithm, several alternative approaches have been developed to address its limitations. The "patience diff" algorithm, introduced by Bram Cohen (creator of BitTorrent), takes a different approach: it first matches lines that appear exactly once in both files (anchoring on unique lines), then recursively diffs the sections between matches. This produces more intuitive diffs for code because unique lines like function signatures and class declarations serve as natural alignment points, preventing the confusing "misaligned" diffs that Myers sometimes produces. The "histogram diff" algorithm, used by JGit and available in Git, extends patience diff by handling lines that appear multiple times using frequency analysis, choosing low-frequency lines as anchors.

Diff output comes in several standard formats. The unified diff format, introduced by Wayne Davison and now the default in most tools, shows changes with context: lines beginning with "-" are deletions, "+" are additions, and unmarked lines provide surrounding context. The @@ header lines indicate positions in both files. Side-by-side format displays the two versions in parallel columns, which many people find easier to read for small changes. The context diff format, predating unified diffs, uses "!" to mark changed lines and provides explicit before/after sections.

Version control systems like Git use diff algorithms not just for display but for fundamental operations. Git's three-way merge uses a common ancestor to determine which side made each change, applying both sets of non-conflicting diffs to produce the merged result. When both sides modify the same region, a merge conflict occurs. Git's "rerere" (reuse recorded resolution) feature remembers how you resolved previous conflicts and can automatically apply the same resolution, demonstrating how diff and merge are intimately connected.

Character-level (or word-level) diffs provide finer granularity than line-level diffs. When a single word changes in a long line, a line-level diff marks the entire line as changed, while a character-level diff highlights only the modified characters. Most modern diff tools use a two-pass approach: first computing line-level diffs, then running a second character-level diff within changed line pairs to pinpoint exact modifications.