Ну... я, как человек ленивый, сделал бы три скрипта. Первый - считывать исходный файл по 100'000 записей, сортировать и записывать в отдельные файлы. Второй - брать по два файла, сливать их с сортировкой в один, пока не останется один сортированный файл. Третий - читать два уже отсортированных файла и выводить разницу между ними.