> I wonder to what extent this is driven at the level of the algorithm.
Almost entirely.
Most programming diff algorithms operate on a line-by-line basis. That means that a single character change in a line marks the whole line as changed. For prose, a single 'line' is usually a paragraph, so it's pretty obvious why they don't work well. You might check out gnu `wdiff` for what a word-by-word diff could look like. I haven't really looked into the area deeply, so I don't know what the state of the art is.
This makes me wonder if anyone has implemented diff by comparing the Abstract Syntax Trees of the two code-bases. I guess it's probably easier than regular diff (assuming you've already got the ASTs from somewhere).
I would think diffing trees would be necessarily more complex than diffing lines - you can think of the line-by-line description of a file as a tree with at most one child per node, so any algorithm for diffing trees should also automatically be able to diff lines.
Tree diff algorithms definitely exist (I know React.js uses diffs on a virtual DOM to minimize operations), but I'm not sure what the state of the art is for those.
Tree diff varies between O(N^2) and O(N^4) for simple solutions of varying complexity of matches possible, with a complex fully general algorithms coming in at O(N^2 log^2 N).
Tree diff is harder because the range of operations is bigger.
React.js cheats by insisting on keys for arrays so matching is much easier.
Almost entirely.
Most programming diff algorithms operate on a line-by-line basis. That means that a single character change in a line marks the whole line as changed. For prose, a single 'line' is usually a paragraph, so it's pretty obvious why they don't work well. You might check out gnu `wdiff` for what a word-by-word diff could look like. I haven't really looked into the area deeply, so I don't know what the state of the art is.