Right now I suspect this is why we are losing so badly to MyersDiff.  Sorting the lines is O(N log N).  MyersDiff is able to run in O(N) time.  Switching this to being a hashtable and trying to get O(N) construction time may help things considerably.