Что-то, что может ускорить вашу сортировку, - это изменить сценарий создания данных, чтобы поместить данные в разные файлы на основе всех или префикса ключа, который будет использоваться для сортировки записей.
Затем, когда вы на самом деле сортируете записи, вы можете ограничить сортировку только работой с небольшими файлами, что (в значительной степени) изменит ваше время сортировки с O( f(N) ) на O( f(n0) + f(n1) + ... ), что для любого f() более сложного чем f(x)=x должно быть меньше (быстрее).
Это также откроет возможность одновременной сортировки файлов, поскольку время ожидания дискового ввода-вывода для одного потока сортировки было бы отличным временем для другого потока, чтобы фактически отсортировать загруженные записи.
Вам необходимо найти удачный баланс между слишком большим количеством файлов и слишком маленькими файлами. 256 файлов - хорошая отправная точка.
Еще одна вещь, которую вы, возможно, захотите исследовать, это ваш алгоритм сортировки. Сортировка слиянием хороша для сортировки вторичного хранилища. Сортировка выбора замены также является хорошим алгоритмом для сортировки вторичного хранилища.
http://www.cs.auckland.ac.nz/software/AlgAnim/niemann/s_ext.htm
Выполнение файлового ввода-вывода большими кусками (лучше всего выровненные по размеру блоки файловой системы) также в большинстве случаев.
Если вам все равно нужно использовать реляционную базу данных, вы можете просто пойти дальше и начать все сначала. СУРБД обычно имеют очень хорошие алгоритмы для обработки всего этого сложного материала.