Цепочки возрастающей длины

При осуществлении упорядочения с использованием внешних запоминающих устройств, когда решающим будет не число сравнений, а объем вводимой и выводимой информации, можно воспользоваться аналогичным методом, но в этом случае промежуточные цепочки на каждом этапе объединения должны быть почти поровну поделены между двумя (или более) лентами. Тогда, после окончания перебора всех элементов те ленты, на которые записывались промежуточные цепочки, могут быть перемотаны и записанная на них информация может считаться исходной для очередного этапа: объединения.
Если с каждой ленты последовательно считывается по одному элементу информации, производится сравнение ключей, и элемент, имеющий меньшее значение ключа, засылается на одну из нескольких лент для промежуточных результатов, то так же, как и при объединении в оперативной памяти, могут быть сформированы цепочки возрастающей длины. Если имеется 26 лент, число переборов всей информации будет равно, где лент используется одновременно под считывание и столько же под запись результата промежуточного объединения.

Вообще говоря, лучше всего упорядочение выполнять в оперативной памяти и при этом стараться получать упорядоченные цепочки максимальной длины. Если имеется возможность одновременно обрабатывать в оперативном запоминающем устройстве только два элемента, может оказаться выгодным внести изменения в метод Гольдштейна — фон Неймана с тем, чтобы обеспечить возможность продолжения формирования цепочки, пока последовательность ключей монотонна.
Эта цепочка должна записываться на одну из лент для промежуточных результатов. Следующая цепочка, длина которой также зависит от последовательности значений, запишется на другую ленту и т. д. После того как будет обработана вся исходная информация, ленты, с которых она считывалась и на которые записывались промежуточные результаты, меняются ролями.

Источник: delete-it