А чем вас не устроили классические алгоритмы сортировки последовательностей (см. Д. Кнут, т. 3)? Вполне себе классический случай. Ключевые слова «однофазная»/«многофазная» «однопутевая», «двухпутевая», «турнирная» сортировка.
В качестве экзотики можно сделать вариант с комбинированной сортировкой (чтение блоков, частичная сортировка, смешивание, например как
здесь). Но работать будет долго.
Если есть опасение, что одна строка не влезет в ограничение по памяти — стройте индекс и сортируйте его.
