Ну я бы сделал так.
Читать сроку, запоминать ее смещение от начала файла (int32), длину строки (int32), а время перевести в timestamp (int32) = ~12 байт на запись (+ оверхед явовских контейнеров)
Сортировать все скопом по timestamp в один контейнер.
И бежать по индексу выкусывая из исходного файла сроки по смещению и длине, добавляя их в новый.
В 512 Мб влезет ~44 млн. срок. (без учета оверхеда контейнеров)