Как быстро найти различия между двумя почти идентичными файлами?

Если у вас есть два в основном идентичных файла с тысячами записей, как вы будете писать код, чтобы находить различия между ними. Предположим, что использование команд unix / linux запрещено.

Моя идея:

Поскольку большинство записей одинаковы, мы можем отсортировать записи в двух файлах, а затем сравнить каждую запись одну за другой, например запись i в файле1 сравнивается с записью i в файле2. Это O (n lg n), n - размер файла.

Есть ли решение O (n)?