Имеется файл, скажем, размеров в 16 Гб, содержащий double
через пробелы.
Простое применение внешней сортировки:
- Разбить файл на куски, которые помещаются в памяти, отсортировать их и обратно записать;
- Применить k-путевое слияние для этих отсортированных кусков и записывать во второй файл.
- Удалить первый файл и переименовать второй.
Проблем нет, если у пользователя есть свободное место (в данном случае, 16 Гб).
Как можно модифицировать алгоритм так, чтобы дополнительное место не тратилось?
На ум приходит лишь небольшая оптимизация: создать файл размером в 1 кусок, записывать в него. При его заполнении удалить использованные элементы из исходного файла, ну и повторить алгоритм.
Поиск в Google постоянно выдаёт не то, что нужно. (Возможно я плохо ищу). Не могли бы подсказать алгоритм или хотя бы литературу?