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

Question

на этой веб-странице:

http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html

Объедините полученные прогоны вместе в последовательно большие прогоны, пока файл не будет отсортирован.

Как я уже цитировал, как мы можем объединить полученные прогоны вместе ???У нас не так много памяти.

Answer 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 и продолжайте, пока вы не выведете весь отсортированный список.

Answer 2

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