Внешняя сортировка

Ответ 1

Представьте, что у вас есть цифры 1 - 9

9  7  2  6  3  4  8  5  1

И пусть предположим, что только 3 поместится в память за раз.

Таким образом, вы разбиваете их на куски по 3 и сортируете каждый, сохраняя каждый результат в отдельном файле:

279
346
158

Теперь вы откроете каждый из трех файлов в виде потоков и прочитаете первое значение из каждого:

2 3 1

Выведите самое низкое значение 1 и получите следующее значение из этого потока, теперь у вас есть:

2 3 5

Выведите следующее нижнее значение 2 и продолжайте движение до тех пор, пока вы не выведете весь отсортированный список.

Ответ 2

Если вы обрабатываете два прогона A и B в какой-то более крупный прогон C, вы можете делать это по очереди, последовательно увеличивая количество прогонов, но все равно только чтение не более 2 строк за раз. Поскольку процесс является итеративным, и поскольку вы работаете с потоками данных, а не с полным сокращением данных, вам не нужно беспокоиться об использовании памяти. С другой стороны, доступ к диску может сделать весь процесс медленным, но он уверен, что не сможет выполнить работу в первую очередь.