Meu palpite é que você simplesmente não classificou os arquivos. Esse é um dos comportamentos que você pode obter em uma entrada não classificada:
$ cat file1
foo
bar
$ cat file2
bar
foo
$ $ diff file1 file2
1d0
< foo
2a2
> foo
Mas, se você classificar:
$ diff <(sort file1) <(sort file2)
$
O trabalho do programa diff
é dizer se dois arquivos são idênticos e, se não, onde eles diferem. Não foi projetado para encontrar semelhanças entre linhas diferentes. Se a linha X de um arquivo não for igual à linha X do outro, os arquivos não serão os mesmos. Não importa se eles contêm exatamente as mesmas informações, se essas informações forem organizadas de maneira diferente, os arquivos serão relatados como diferentes.