Java предоставляет процедуру сортировки общего назначения, которую можно использовать как часть более широкого решения вашей проблемы. Общий подход к сортировке данных, которые слишком велики, чтобы вместить их в память, таков:
1) Считайте столько данных, сколько уместится в основную память, скажем, 1 Гб
2) Быстрая сортировка 1 Гб (здесь вы бы использовали встроенную сортировку Java из среды Collections)
3) Записать отсортированный 1 Гб на диск как "chunk-1"
4) Повторяйте шаги 1-3, пока не пройдете все данные, сохранив каждый блок данных в отдельном файле. Таким образом, если ваши исходные данные были 9 Гб, теперь у вас будет 9 отсортированных фрагментов данных, помеченных как «chunk-1» через «chunk-9»
5) Теперь вам просто нужна последняя сортировка слиянием, чтобы объединить 9 отсортированных фрагментов в один полностью отсортированный набор данных. Сортировка слиянием будет очень эффективно работать с этими предварительно отсортированными фрагментами. По сути, он откроет 9 файловых ридеров (по одному на каждый блок), плюс один файловый ридер (для вывода). Затем он сравнивает первый элемент данных в каждом прочитанном файле и выбирает наименьшее значение, которое записывается в выходной файл. Считыватель, из которого поступило это выбранное значение, переходит к следующему элементу данных, и повторяется 9-сторонний процесс сравнения, чтобы найти наименьшее значение, снова записывая ответ в выходной файл. Этот процесс повторяется до тех пор, пока все данные не будут прочитаны из всех файлов чанка.
6) Как только шаг 5 завершит чтение всех данных, которые вы сделали - ваш выходной файл теперь содержит полностью отсортированный набор данных
При таком подходе вы можете легко написать собственную утилиту "megasort", которая принимает имя файла и параметр maxMemory и эффективно сортирует файл, используя временные файлы. Могу поспорить, что вы могли бы найти хотя бы несколько реализаций для этого, но если нет, вы можете просто свернуть свои собственные, как описано выше.