Many years ago, I wrote a some code that made pack files with out of order copy commands. (Just messing around in Go trying to learn how pack files worked.)

I was too lazy to implement the diffing algorithm, so I used the suffixarray from the go standard library and greedily grabbed the longest match at each point in the input. It's been a while, but I think I got a 12% improvement on my test case. (Probably wouldn't do that well in general.)

I'm assumed the git code just runs off of a diff (longest common substring), but I never checked.