Решал эту задачу в реальном проекте в 2000-е. Но писал на C, поэтому мог позволить себе все. Да и исходный файл делал сам из других данных, так что мог его портить. Кроме того, надо было получить возможность доступа в порядке отсортированности, а собственно передвижение строк не требовалось.
Решение
Открываем file mapping и view на весь файл.
За линейное время проходим весь файл, заменяем разделитель внутри строки на '\0'. Конец строки тоже заменяем на '\0'. Одновременно строим массив указателей (смещение от начала файла + базовый адрес view) для каждой строки.
Этот массив и сортируем обычной qsort, используя strcmp в качестве int (*compare), так как строка заканчивается '\0'. Если strcmp возвращает 0 для первого критерия, strcmp по второму критерию.
Потом можно пройти файл заново, вернуть концы строк и разделители, но мне это было не нужно.
Если таки нужен выходной файл — пройти массив указателей линейно, переписывая строки в новый файл.
P.S. В действительности все было немного иначе. Полей в строке было 5-6 штук и надо было отсортировать по каждому полю. Так что массивов указателей было столько же и каждый сортировался.
