Сортировка файла большего размера с меньшим объемом оперативной памяти

Предположим, нам нужно отсортировать файл случайных целых чисел размером 1 ГБ, а доступный размер оперативной памяти составляет 200 МБ. Как это будет сделано?

Самый простой способ сделать это - использовать внешнюю сортировку .
Мы разделяем наш исходный файл на временные файлы размером, равным размеру оперативной памяти, и сначала сортируем эти файлы.
Предположим, 1 ГБ = 1024 МБ, поэтому мы выполняем следующие шаги.

1. Разделите исходный файл на 5 небольших временных файлов, каждый размером 200 МБ (т. Е. Равных размеру оперативной памяти).
2. Отсортируйте эти временные файлы по одному, используя оперативную память по отдельности (любой алгоритм сортировки: быстрая сортировка, сортировка слиянием).

Теперь у нас есть небольшие отсортированные временные файлы, как показано на изображении ниже.

Теперь мы отсортировали временные файлы .

1. Указатели инициализируются в каждом файле
2. Создается новый файл размером 1 ГБ (размер исходного файла).
3. Первый элемент сравнивается из каждого файла с указателем.
4. Наименьший элемент копируется в новый файл размером 1 ГБ, а указатель увеличивается в файле, который указывает на этот наименьший элемент.
5. Тот же процесс выполняется до тех пор, пока все указатели не пройдут через соответствующие файлы.
6. Когда все указатели пройдены, у нас есть новый файл с 1 ГБ отсортированных целых чисел.

Таким образом можно отсортировать любой файл большего размера, когда есть ограничение на размер первичной памяти (RAM).

Основная идея состоит в том, чтобы разделить более крупный файл на временные файлы меньшего размера, отсортировать временные файлы и затем создать новый файл, используя эти временные файлы. Этот вопрос был задан Infosys в интервью для профайла опытного программиста.