на этой веб-странице:
http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html
Объедините полученные результаты вместе последовательно увеличиваются, пока файл сортируется.
Как я процитировал, как мы можем объединить полученные результаты вместе? У нас не так много памяти.
Представьте, что у вас есть цифры 1 - 9
9 7 2 6 3 4 8 5 1
И пусть предположим, что только 3 поместится в память за раз.
Таким образом, вы разбиваете их на куски по 3 и сортируете каждый, сохраняя каждый результат в отдельном файле:
279
346
158
Теперь вы откроете каждый из трех файлов в виде потоков и прочитаете первое значение из каждого:
2 3 1
Выведите самое низкое значение 1 и получите следующее значение из этого потока, теперь у вас есть:
2 3 5
Выведите следующее нижнее значение 2 и продолжайте движение до тех пор, пока вы не выведете весь отсортированный список.
Если вы обрабатываете два прогона A и B в какой-то более крупный прогон C, вы можете делать это по очереди, последовательно увеличивая количество прогонов, но все равно только чтение не более 2 строк за раз. Поскольку процесс является итеративным, и поскольку вы работаете с потоками данных, а не с полным сокращением данных, вам не нужно беспокоиться об использовании памяти. С другой стороны, доступ к диску может сделать весь процесс медленным, но он уверен, что не сможет выполнить работу в первую очередь.