\input style
\chapnotrue
\chapno=5\subchno=4\subsubchno=6

1) пРИВЕДЕННЫЕ ФОРМУЛЫ ПОКАЗЫВАЮТ, ЧТО СОРТИРОВКА ЯВЛЯЕТСЯ, В СУЩНОСТИ, 
ФУНКЦИЕЙ ОТ ПРОИЗВЕДЕНИЯ~$N$ И~$C$, А НЕ ОТ~$N$ И~$C$ ПОРОЗНЬ. зА 
ИСКЛЮЧЕНИЕМ НЕСКОЛЬКИХ ОТНОСИТЕЛЬНО НЕЗНАЧИТЕЛЬНЫХ СООБРАЖЕНИЙ (НАПРИМЕР,
 ЧТО $B$~ВЫБИРАЕТСЯ КРАТНЫМ $C$), ИЗ НАШИХ ФОРМУЛ СЛЕДУЕТ, ЧТО 
СОРТИРОВКА ОДНОГО МИЛЛИОНА ЗАПИСЕЙ ПО 10 ЛИТЕР КАЖДАЯ ЗАЙМЕТ ПРИМЕРНО 
СТОЛЬКО ЖЕ ВРЕМЕНИ, ЧТО И СОРТИРОВКА 100000 ЗАПИСЕЙ ПО 100 ЛИТЕР КАЖДАЯ. 
нА САМОМ ДЕЛЕ ЗДЕСЬ МОЖЕТ ПОЯВИТЬСЯ РАЗЛИЧИЕ, НЕ ОБНАРУЖИМОЕ В 
НАШИХ ФОРМУЛАХ, ТАК КАК ВО ВРЕМЯ ВЫБОРА С ЗАМЕЩЕНИЕМ 
НЕКОТОРОЕ ПРОСТРАНСТВО ИСПОЛЬЗУЕТСЯ ДЛЯ ПОЛЕЙ СВЯЗИ. в ЛЮБОМ СЛУЧАЕ РАЗМЕР 
\emph{КЛЮЧА} ЕДВА ЛИ ОКАЖЕТ КАКОЕ-ЛИБО ВЛИЯНИЕ, ЕСЛИ ТОЛЬКО КЛЮЧИ НЕ БУДУТ 
СТОЛЬ ДЛИННЫМИ И СЛОЖНЫМИ, ЧТО ВНУТРЕННИЕ ВЫЧИСЛЕНИЯ НЕ СМОГУТ УГНАТЬСЯ ЗА 
ЛЕНТАМИ.

пРИ ДЛИННЫХ ЗАПИСЯХ И КОРОТКИХ КЛЮЧАХ СОБЛАЗНИТЕЛЬНО ВЫДЕЛИТЬ КЛЮЧИ, 
ОТСОРТИРОВАТЬ ИХ, А ЗАТЕМ КАК-НИБУДЬ ПЕРЕСТАВИТЬ ЗАПИСИ ЦЕЛИКОМ. нО ЭТА 
ИДЕЯ, КАЖЕТСЯ, НЕ РАБОТАЕТ: ОНА МОЖЕТ ТОЛЬКО ОТСРОЧИТЬ АГОНИЮ, ПОСКОЛЬКУ 
ПРОЦЕДУРА ОКОНЧАТЕЛЬНОЙ ПЕРЕСТАНОВКИ ТРЕБУЕТ ПОЧТИ СТОЛЬКО ЖЕ ВРЕМЕНИ,
 СКОЛЬКО ПОТРЕБОВАЛА БЫ ОБЩЕПРИНЯТАЯ СОРТИРОВКА СЛИЯНИЕМ.

2) мЫ ВИДЕЛИ, ЧТО ТРЕБУЕТСЯ ОТ~15 ДО~19~МИН, ЧТОБЫ ОТСОРТИРОВАТЬ 
100000~ЗАПИСЕЙ ПО 100~ЛИТЕР ПРИ СОБЛЮДЕНИИ НАШИХ ПРЕДПОЛОЖЕНИЙ. сКОЛЬКО 
ВРЕМЕНИ ЗАНЯЛА БЫ ИХ СОРТИРОВКА НА КАРТОЧНОМ СОРТИРОВЩИКЕ? эТОТ ВОПРОС 
ИМЕЕТ ПРАКТИЧЕСКИЙ ИНТЕРЕС ПОТОМУ, ЧТО КАРТОЧНЫЕ СОРТИРОВЩИКИ ДЕШЕВЛЕ 
эвм. дОПУСКАЯ, ЧТО КАЖДАЯ ЗАПИСЬ МОЖЕТ БЫТЬ ВТИСНУТА В 80-КОЛОННУЮ КАРТУ 
И ЧТО АЛФАВИТНЫЙ КЛЮЧ ЗАНИМАЕТ ШЕСТЬ КОЛОНОК, ПРИЧЕМ
ДЛЯ СОРТИРОВКИ ПО КАЖДОЙ КОЛОНКЕ ТРЕБУЕТСЯ В СРЕДНЕМ $1{2\over3}$~ПРОХОДА, 
ПОЛУЧАЕМ, ЧТО МЫ ДОЛЖНЫ ПРОПУСТИТЬ КАЖДУЮ КАРТУ ЧЕРЕЗ МАШИНУ ПРИМЕРНО 
10~РАЗ. пРИ СКОРОСТИ 1000 КАРТ В МИНУТУ ЭТО ЗАНЯЛО БЫ 1000~МИН, 
Т.~Е.~ПОЧТИ 17~Ч. (иМЕЕТСЯ ВЕСЬМА БОЛЬШАЯ ВЕРОЯТНОСТЬ, ЧТО ЗА ЭТО ВРЕМЯ 
НЕКОТОРЫЕ КАРТЫ ОКАЖУТСЯ НЕЧАЯННО "ПЕРЕПУТАННЫМИ" ИЛИ БУДУТ "ЗАМЯТЫ" В 
МАШИНЕ.)

3) пРИ НАПИСАНИИ ПРОГРАММЫ СОРТИРОВКИ, КОТОРАЯ ДОЛЖНА ИСПОЛЬЗОВАТЬСЯ 
МНОГОКРАТНО, РАЗУМНО ОЧЕНЬ ТЩАТЕЛЬНО ОЦЕНИТЬ ВРЕМЯ РАБОТЫ И СРАВНИТЬ 
ТЕОРИЮ С ДЕЙСТВИТЕЛЬНЫМИ НАБЛЮДАЕМЫМИ ХАРАКТЕРИСТИКАМИ ВЫПОЛНЕНИЯ. тАК 
КАК ТЕОРИЯ СОРТИРОВКИ РАЗВИТА ДОВОЛЬНО ХОРОШО, ТО ЭТА ПРОЦЕДУРА, КАК 
ИЗВЕСТНО, СПОСОБНА ВНЕЗАПНО ВЫЯВИТЬ ДЕФЕКТЫ В ОБОРУДОВАНИИ ИЛИ 
ПРОГРАММНОМ ОБЕСПЕЧЕНИИ ВВОДА/ВЫВОДА В СУЩЕСТВУЮЩИХ 
СИСТЕМАХ. оКАЗЫВАЕТСЯ ОБСЛУЖИВАНИЕ РАБОТАЛО МЕДЛЕННЕЕ, ЧЕМ СЛЕДОВАЛО, И 
НИКТО ЭТОГО НЕ ЗАМЕЧАЛ, ПОКА ЭТО НЕ ПРОЯВИЛОСЬ НА ПРОГРАММЕ СОРТИРОВКИ!

4) нЕКОТОРЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ ИМЕЮТ ДВА "БАНКА"
%%401
ЛЕНТОПРОТЯЖНЫХ УСТРОЙСТВ, ПРИСОЕДИНЕННЫХ К ОТДЕЛЬНЫМ "КАНАЛАМ" ТАКИМ 
СПОСОБОМ, ЧТО ОДНОВРЕМЕННОЕ ЧТЕНИЕ И ЗАПИСЬ ДОПУСКАЕТСЯ ТОЛЬКО ДЛЯ ЛЕНТ ИЗ 
РАЗНЫХ БАНКОВ. дЛЯ ТАКОЙ КОНФИГУРАЦИИ БОЛЬШЕ ВСЕГО ПОДХОДИТ 
СБАЛАНСИРОВАННОЕ СЛИЯНИЕ. рАССМОТРИМ, НАПРИМЕР, СЛУЧАЙ ШЕСТИ ЛЕНТ ПО ТРИ В 
КАЖДОМ БАНКЕ И ПРЕДПОЛОЖИМ, ЧТО МЫ ХОТИМ ВЫПОЛНИТЬ МНОГОФАЗНОЕ СЛИЯНИЕ 
С~$T=6$. вОВРЕМЯ ПЯТИПУТЕВОГО СЛИЯНИЯ ДВЕ ИЗ ВВОДНЫЕ ЛЕНТ БУДУТ НЕ В ТОМ 
БАНКЕ, ТАК ЧТО, ГРУБО ГОВОРЯ, ДВЕ ПЯТЫХ ВРЕМЕНИ ВВОДА НЕ БУДУТ СОВМЕЩЕНЫ С 
ВЫВОДОМ. эТО ДОБАВЛЯЕТ КО ВРЕМЕНИ СОРТИРОВКИ ПРИБЛИЗИТЕЛЬНО 40\%, ТАК ЧТО 
СБАЛАНСИРОВАННОЕ СЛИЯНИЕ ОКАЖЕТСЯ ЛУЧШЕ МНОГОФАЗНОГО ДАЖЕ В 
СЛУЧАЕ ОБРАТНОГО ЧТЕНИЯ.

5) нАШ АНАЛИЗ ВЫБОРА С ЗАМЕЩЕНИЕМ БЫЛ ВЫПОЛНЕН ДЛЯ "СЛУЧАЙНЫХ" ФАЙЛОВ, НО 
ФАЙЛЫ, ВСТРЕЧАЮЩИЕСЯ НА ПРАКТИКЕ, ОЧЕНЬ ЧАСТО УЖЕ УПОРЯДОЧЕНЫ В ТОЙ ИЛИ 
ИНОЙ СТЕПЕНИ. (фАКТИЧЕСКИ ИНОГДА ЛЮДИ БУДУТ СОРТИРОВАТЬ ФАЙЛЫ, УЖЕ 
УПОРЯДОЧЕННЫЕ, ТОЛЬКО ЧТОБЫ УБЕДИТЬСЯ В ЭТОМ.) тАКИМ ОБРАЗОМ, ОПЫТ ДАЖЕ 
В БОЛЬШЕЙ МЕРЕ, ЧЕМ УКАЗЫВАЮТ НАШИ ФОРМУЛЫ, ПОКАЗАЛ, ЧТО ВЫБОР С 
ЗАМЕЩЕНИЕМ ПРЕДПОЧТИТЕЛЬНЕЕ ДРУГИХ ВИДОВ ВНУТРЕННЕЙ СОРТИРОВКИ. эТО 
ПРЕИМУЩЕСТВО НЕСКОЛЬКО ОСЛАБЛЯЕТСЯ В СЛУЧАЕ МНОГОФАЗНОЙ СОРТИРОВКИ С 
ОБРАТНЫМ ЧТЕНИЕМ, ТАК КАК ДОЛЖЕН БЫТЬ ПОРОЖДЕН РЯД УБЫВАЮЩИХ ОТРЕЗКОВ; НА 
САМОМ ДЕЛЕ р.~л.~гИЛСТЭД (ОН ПЕРВЫЙ ОПУБЛИКОВАЛ МНОГОФАЗНОЕ 
СЛИЯНИЕ) ПЕРВОНАЧАЛЬНО ПО ЭТОЙ ПРИЧИНЕ ОТВЕРГ МЕТОД ОБРАТНОГО ЧТЕНИЯ. нО 
ПОЗДНЕЕ ОН ЗАМЕТИЛ, ЧТО ЧЕРЕДОВАНИЕ НАПРАВЛЕНИЙ БУДЕТ ВСЕ ЖЕ ДАВАТЬ 
ДЛИННЫЕ ВОЗРАСТАЮЩИЕ ОТРЕЗКИ. кРОМЕ ТОГО, МНОГОФАЗНЫЙ МЕТОД С ОБРАТНЫМ 
ЧТЕНИЕМ---ЭТО ЕДИНСТВЕННЫЙ СТАНДАРТНЫЙ МЕТОД, КОТОРЫЙ БЛАГОСКЛОНЕН К 
УБЫВАЮЩИМ ВХОДНЫМ ФАЙЛАМ, РАВНО КАК И К ВОЗРАСТАЮЩИМ.

6) дРУГОЕ ПРЕИМУЩЕСТВО ВЫБОРА С ЗАМЕЩЕНИЕМ СОСТОИТ В ТОМ, ЧТО ЭТОТ МЕТОД 
ДОПУСКАЕТ СОВМЕЩЕНИЕ ПРОЦЕССОВ ЧТЕНИЯ, ЗАПИСИ И ВЫЧИСЛЕНИЙ. еСЛИ БЫ МЫ 
ПРОСТО ВЫПОЛНЯЛИ ВНУТРЕННЮЮ СОРТИРОВКУ ОЧЕВИДНЫМ СПОСОБОМ---ЗАПОЛНЯЯ 
ПАМЯТЬ, СОРТИРУЯ ЕЕ И ЗАТЕМ ЗАПИСЫВАЯ ЕЕ ПО МЕРЕ ТОГО, КАК ОНА ЗАПОЛНЯЕТСЯ 
НОВЫМ СОДЕРЖИМЫМ,---ТО ПРОХОД РАСПРЕДЕЛЕНИЯ ЗАНЯЛ БЫ ПРИМЕРНО ВДВОЕ БОЛЬШЕ 
ВРЕМЕНИ!

иЗ РАССМОТРЕННЫХ НАМИ МЕТОДОВ ВНУТРЕННЕЙ СОРТИРОВКИ ЕЩЕ ТОЛЬКО ОДИН МОЖНО 
ПРИСПОСОБИТЬ К ОДНОВРЕМЕННОМУ ЧТЕНИЮ, ЗАПИСИ И ВЫЧИСЛЕНИЯМ---ПИРАМИДАЛЬНУЮ 
СОРТИРОВКУ. (эТА ИДЕЯ БЫЛА ИСПОЛЬЗОВАНА ПРИ ПОДГОТОВКЕ ПРИМЕРА~10 
СХЕМЫ~а.) пРЕДПОЛОЖИМ ДЛЯ УДОБСТВА, ЧТО ВНУТРЕННЯЯ ПАМЯТЬ СОДЕРЖИТ 
1000~ЗАПИСЕЙ, А КАЖДЫЙ БЛОК НА ЛЕНТЕ---ПО 100. дЕЙСТВОВАТЬ МОЖНО СЛЕДУЮЩИМ 
ОБРАЗОМ (ЧЕРЕЗ $B_1$, $B_2$,~\dots, $B_{10}$ ОБОЗНАЧЕНО СОДЕРЖИМОЕ ПАМЯТИ, 
 РАЗДЕЛЕННОЙ НА 10~БЛОКОВ ПО 100~ЗАПИСЕЙ).

%% 402

{\sl шАГ 0.\/} зАПОЛНИТЬ ПАМЯТЬ И СДЕЛАТЬ ТАК, ЧТОБЫ ЭЛЕМЕНТЫ $B_2$\dots 
$B_{10}$ УДОВЛЕТВОРЯЛИ НЕРАВЕНСТВАМ ПИРАМИДЫ (С НАИМЕНЬШИМ ЭЛЕМЕНТОМ В ВЕРШИНЕ).

{\sl шАГ 1.\/} сВЕСТИ $B_1$\dots$B_{10}$ В ПИРАМИДУ, ЗАТЕМ ВЫБРАТЬ 
НАИМЕНЬШИЕ 100 ЗАПИСЕЙ И ПЕРЕПИСАТЬ ИХ В $B_{10}$.

{\sl шАГ 2.\/} зАПИСАТЬ ИЗ $B_{10}$; В ТО ЖЕ ВРЕМЯ ВЫБРАТЬ НАИМЕНЬШИЕ 100 
ЗАПИСЕЙ ИЗ $B_1$\dots$B_{9}$ И ПОМЕСТИТЬ ИХ В $B_9$.

{\sl шАГ 3.\/} пРОЧИТАТЬ В~$B_{10}$ И ЗАПИСАТЬ ИЗ $B_9$; В ТО ЖЕ 
ВРЕМЯ ВЫБРАТЬ НАИМЕНЬШИЕ 100~ЗАПИСЕЙ ИЗ $B_1$\dots$B_8$ И ПОМЕСТИТЬ ИХ В~$B_8$.

\dots

{\sl шАГ 9.\/} пРОЧИТАТЬ В $B_4$ И ЗАПИСАТЬ ИЗ~$B_3$; В ТО ЖЕ 
ВРЕМЯ ВЫБРАТЬ НАИМЕНЬШИЕ 100~ЗАПИСЕЙ ИЗ $B_1$ $B_2$, ПОМЕСТИТЬ ИХ В $B_2$ 
И СДЕЛАТЬ ТАК, ЧТОБЫ НЕРАВЕНСТВА ПИРАМИДЫ БЫЛИ СПРАВЕДЛИВЫ ДЛЯ $B_5$\dots$B_{10}$.

{\sl шАГ 10.\/} пРОЧИТАТЬ В~$B_3$ И ЗАПИСАТЬ ИЗ~$B_2$, СОРТИРУЯ~$B_1$, В 
ТО ЖЕ ВРЕМЯ СДЕЛАТЬ ТАК, ЧТОБЫ НЕРАВЕНСТВА ПИРАМИДЫ БЫЛИ СПРАВЕДЛИВЫ ДЛЯ $B4$\dots$B_{10}$.

{\sl шАГ 11.\/} пРОЧИТАТЬ В~$B_2$ И ЗАПИСАТЬ ИЗ~$B_1$; В ТО ЖЕ 
ВРЕМЯ СДЕЛАТЬ ТАК, ЧТОБЫ $B_3$\dots$B_{10}$ УДОВЛЕТВОРЯЛИ НЕРАВЕНСТВАМ ПИРАМИДЫ.

{\sl шАГ 12.\/} пРОЧИТАТЬ В~$B_1$, ДЕЛАЯ ТАК, ЧТОБЫ $B_2$\dots$B_{10}$ 
УДОВЛЕТВОРЯЛИ НЕРАВЕНСТВАМ ПИРАМИДЫ. вЕРНУТЬСЯ К ШАГУ 1. \endmark

7) мЫ ПРЕДПОЛАГАЕМ, ЧТО ЧИСЛО СОРТИРУЕМЫХ ЗАПИСЕЙ~$N$ НЕ ИЗВЕСТНО ЗАРАНЕЕ. 
нА САМОМ ЖЕ ДЕЛЕ В БОЛЬШИНСТВЕ ВЫЧИСЛИТЕЛЬНЫХ МАШИН ЕСТЬ ВОЗМОЖНОСТЬ ВСЕ 
ВРЕМЯ СЛЕДИТЬ ЗА ЧИСЛОМ ЗАПИСЕЙ ВО ВСЕХ ФАЙЛАХ, И МЫ МОГЛИ БЫ СЧИТАТЬ, ЧТО 
НАША ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА СПОСОБНА СООБЩИТЬ ЗНАЧЕНИЕ~$N$. нАСКОЛЬКО БЫ 
НАМ ЭТО ПОМОГЛО? к СОЖАЛЕНИЮ, НЕ ОЧЕНЬ! мЫ ВИДЕЛИ, ЧТО  ВЫБОР С ЗАМЕЩЕНИЕМ 
ВЕСЬМА ВЫГОДЕН, НО ОН ВЕДЕТ К НЕПРЕДСКАЗУЕМОМУ ЧИСЛУ НАЧАЛЬНЫХ ОТРЕЗКОВ. в 
СБАЛАНСИРОВАННОМ СЛИЯНИИ МЫ МОГЛИ БЫ ИСПОЛЬЗОВАТЬ ИНФОРМАЦИЮ ОБ~$N$ ДЛЯ 
УСТАНОВЛЕНИЯ ТАКОГО РАЗМЕРА БУФЕРА~$B$, ЧТОБЫ $S$~ОКАЗАЛОСЬ, СКОРЕЕ ВСЕГО, 
ЧУТЬ МЕНЬШЕ СТЕПЕНИ~$P$; В МНОГОФАЗНОМ РАСПРЕДЕЛЕНИИ С 
ОПТИМАЛЬНЫМ РАЗМЕЩЕНИЕМ ФИКТИВНЫХ ОТРЕЗКОВ МЫ МОГЛИ БЫ 
ИСПОЛЬЗОВАТЬ ИНФОРМАЦИЮ ОБ~$N$, ЧТОБЫ РЕШИТЬ, КАКОЙ УРОВЕНЬ ВЫБРАТЬ (СМ. 
ТАБЛ. 5.4.2-2).

иДЯ ПО ДРУГОМУ ПУТИ И НЕ ИСПОЛЬЗУЯ ВЫБОРА С ЗАМЕЩЕНИЕМ, МЫ МОГЛИ БЫ 
ПРИМЕНИТЬ СЛИЯНИЕ В ПРЯМОМ ПОРЯДКЕ, ОПИСАННОЕ В КОНЦЕ П.~5.4.4, ВСТРОИВ 
ЕГО В ОСЦИЛЛИРУЮЩУЮ СОРТИРОВКУ, РАСПРЕДЕЛЯЮЩУЮ НАЧАЛЬНЫЕ ОТРЕЗКИ 
СООТВЕТСТВУЮЩЕГО НАПРАВЛЕНИЯ В СООТВЕТСТВУЮЩИЙ МОМЕНТ (ВМЕСТО ТОГО ЧТОБЫ 
БРАТЬ ИХ С "ЛЕНТЫ~$A$", КАК ОПИСАНО). эТОТ МЕТОД, В СУЩНОСТИ, 
\emph{ОПТИМАЛЕН} СРЕДИ ВСЕХ МЕТОДОВ, ВЫПОЛНЯЮЩИХ ВНУТРЕННЮЮ СОРТИРОВКУ 
БЕЗ ВЫБОРА С ЗАМЕЩЕНИЕМ, ТАК КАК ОН СЛИВАЕТ В СООТВЕТСТВИИ С НАИЛУЧШИМ 
ВОЗМОЖНЫМ $P\hbox{-АРНЫМ}$ ДЕРЕВОМ, НО ОН ВСЕ ЖЕ РАБОТАЕТ МЕДЛЕННЕЙ 
МЕТОДОВ, ОСНОВАННЫХ НА ВЫБОРЕ С ЗАМЕЩЕНИЕМ.

%% 403

8) лЕНТОПРОТЯЖНЫЕ УСТРОЙСТВА ЧАСТО ОКАЗЫВАЮТСЯ НАИМЕНЕЕ НАДЕЖНЫМИ ЧАСТЯМИ 
эвм. оБСЛУЖИВАЮЩИЙ ПЕРСОНАЛ ОБЫЧНО ПОЛУЧАЕТ ВЫЗОВЫ ДЛЯ ИСПРАВЛЕНИЯ 
ЛЕНТОПРОТЯЖНЫХ УСТРОЙСТВ ЧАЩЕ, ЧЕМ ДЛЯ ЛЮБОГО ДРУГОГО КОМПОНЕНТА МАШИНЫ, И 
ОПЕРАТОРЫ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ ДОЛЖНЫ УМЕТЬ ВОЗОБНОВЛЯТЬ РАБОТУ ПОСЛЕ 
СБОЯ ЛЕНТЫ. аВТОР НИКОГДА ДАЖЕ НЕ ВИДЕЛ УСТАНОВОК С~10 ИЛИ БОЛЕЕ 
ЛЕНТОПРОТЯЖНЫМИ УСТРОЙСТВАМИ, КОТОРЫЕ БЫ ВСЕ ОДНОВРЕМЕННО НАХОДИЛИСЬ В 
ХОРОШЕМ РАБОЧЕМ СОСТОЯНИИ. сЛЕДОВАТЕЛЬНО, МОЖНО ПРИНЯТЬ ЗА АКСИОМУ, ЧТО 
\emph{ИСХОДНАЯ ВВОДНАЯ ЛЕНТА НИ В КОЕМ СЛУЧАЕ НЕ ДОЛЖНА ИЗМЕНЯТЬСЯ, ПОКА 
НЕ СТАНЕТ ИЗВЕСТНО, ЧТО ВСЯ СОРТИРОВКА УДОВЛЕТВОРИТЕЛЬНО ЗАВЕРШЕНА.} в 
НЕКОТОРЫХ ПРИМЕРАХ СХЕМЫ~A СУЩЕСТВУЕТ ДОСАДНОЕ "ВРЕМЯ, ПОКА ОПЕРАТОР НЕ 
СМЕНИТ ЛЕНТУ", НО БЫЛО БЫ СЛИШКОМ РИСКОВАННО ЗАТИРАТЬ ИСХОДНЫЕ ДАННЫЕ 
ВВИДУ ВОЗМОЖНОСТИ КАКОЙ-ЛИБО НЕИСПРАВНОСТИ ВО ВРЕМЯ ДЛИННОЙ СОРТИРОВКИ.

9) пРИ ПЕРЕХОДЕ ОТ ПРЯМОЙ ЗАПИСИ К ОБРАТНОМУ ЧТЕНИЮ МЫ МОЖЕМ СЭКОНОМИТЬ 
НЕКОТОРОЕ ВРЕМЯ, ВОВСЕ НЕ ЗАПИСЫВАЯ ПОСЛЕДНИЙ БУФЕР НА ЛЕНТУ; ОН В ЛЮБОМ 
СЛУЧАЕ БУДЕТ ВНОВЬ ПРОЧИТАН! сХЕМА~A ПОКАЗЫВАЕТ, ЧТО ЭТОТ ПРИЕМ В 
ДЕЙСТВИТЕЛЬНОСТИ ЭКОНОМИТ СРАВНИТЕЛЬНО НЕМНОГО ВРЕМЕНИ, ЗА ИСКЛЮЧЕНИЕМ 
СЛУЧАЯ ОСЦИЛЛИРУЮЩЕЙ СОРТИРОВКИ, КОГДА НАПРАВЛЕНИЯ МЕНЯЮТСЯ ЧАСТО.

10) еСЛИ В НАШЕМ РАСПОРЯЖЕНИИ МНОГО ЛЕНТОЧНЫХ УСТРОЙСТВ, ТО НЕ ВСЕГДА 
СТОИТ ИСПОЛЬЗОВАТЬ ИХ ВСЕ В ЦЕЛЯХ ПОЛУЧЕНИЯ "ВЫСОКОГО ПОРЯДКА СЛИЯНИЯ". 
тАК, НАПРИМЕР, БОЛЕЕ ВЫСОКИЙ ПОРЯДОК СЛИЯНИЯ ОБЫЧНО ОЗНАЧАЕТ МЕНЬШИЙ 
РАЗМЕР БЛОКА, А ПРОЦЕНТНАЯ РАЗНОСТЬ МЕЖДУ $\log_P S$ И~$\log_{P+1} S$ НЕ 
ОЧЕНЬ ВЕЛИКА ПРИ БОЛЬШИХ~$P$. пОДУМАЙТЕ ТАКЖЕ О БЕДНОМ ОПЕРАТОРЕ эвм, 
КОТОРЫЙ ДОЛЖЕН УСТАНОВИТЬ ВСЕ ЭТИ РАБОЧИЕ ЛЕНТЫ. с ДРУГОЙ СТОРОНЫ, В 
УПР.~12 ОПИСАН ИНТЕРЕСНЫЙ СПОСОБ ИСПОЛЬЗОВАНИЯ ДОПОЛНИТЕЛЬНЫХ 
ЛЕНТОПРОТЯЖНЫХ УСТРОЙСТВ, ГРУППИРУЕМЫХ ТАК. ЧТОБЫ СОВМЕСТИТЬ ВРЕМЯ ВВОДА 
И ВЫВОДА БЕЗ УВЕЛИЧЕНИЯ ПОРЯДКА СЛИЯНИЯ.

11) нА МАШИНАХ, ПОДОБНЫХ \MIX, КОТОРЫЕ ИМЕЮТ ФИКСИРОВАННЫЙ И ДОВОЛЬНО 
МАЛЕНЬКИЙ РАЗМЕР БЛОКОВ, ДЛЯ СЛИЯНИЯ ЕДВА ЛИ ТРЕБУЕТСЯ МНОГО ВНУТРЕННЕЙ 
ПАМЯТИ. зДЕСЬ ОСЦИЛЛИРУЮЩАЯ СОРТИРОВКА БОЛЕЕ ПРЕДПОЧТИТЕЛЬНА; пОТОМУ ЧТО 
СТАНОВИТСЯ ВОЗМОЖНЫМ СОХРАНЯТЬ ДЕРЕВО ВЫБОРА С ЗАМЕЩЕНИЕМ В ПАМЯТИ ВО 
ВРЕМЯ СЛИЯНИЯ. нА САМОМ ДЕЛЕ В ЭТОМ СЛУЧАЕ МОЖНО 
УСОВЕРШЕНСТВОВАТЬ ОСЦИЛЛИРУЮЩУЮ СОРТИРОВКУ (КАК ПРЕДЛОЖИЛ к.~дЖ.~бЕЛЛ В 
1962~Г.), СЛИВАЯ НОВЫЙ НАЧАЛЬНЫЙ ОТРЕЗОК В ВЫВОД КАЖДЫЙ РАЗ, КОГДА МЫ 
СЛИВАЕМ С РАБОЧИХ ЛЕНТ!

12) мЫ ВИДЕЛИ, ЧТО ФАЙЛЫ НА НЕСКОЛЬКИХ БОБИНАХ ДОЛЖНЫ СОРТИРОВАТЬСЯ 
ПОСЛЕДОВАТЕЛЬНО БОБИНА ЗА БОБИНОЙ, ЧТОБЫ ИЗБЕЖАТЬ ЧРЕЗМЕРНОЙ РАБОТЫ ПО 
ПЕРЕСТАНОВКЕ ЛЕНТ. фАКТИЧЕСКИ СБАЛАНСИРОВАННОЕ СЛИЯНИЕ С ШЕСТЬЮ ЛЕНТАМИ, 
ЕСЛИ ОНО ТЩАТЕЛЬНО
%% 404
ЗАПРОГРАММИРОВАНО, МОЖЕТ СОРТИРОВАТЬ \emph{ТРИ} БОБИНЫ ДО 
МОМЕНТА ОКОНЧАТЕЛЬНОГО СЛИЯНИЯ.

дЛЯ СЛИЯНИЯ ОТНОСИТЕЛЬНО БОЛЬШОГО ЧИСЛА ОТДЕЛЬНО ОТСОРТИРОВАННЫХ БОБИН 
БЫСТРЕЙШИМ БУДЕТ ДЕРЕВО СЛИЯНИЯ С МИНИМАЛЬНОЙ ДЛИНОЙ ПУТИ (СР. 
С~П.~5.4.4). эТО ПОСТРОЕНИЕ БЫЛО ВПЕРВЫЕ ОСУЩЕСТВЛЕНО э.~X.~фРЭНДОМ [{\sl 
JACM\/}, {\bf 3}(1956), 166--167] И ЗАТЕМ у.~X.~бУРЖЕМ [{\sl Information 
and Control,\/} {\bf 1} (1958), 181--197], КОТОРЫЕ ОТМЕТИЛИ, ЧТО 
ОПТИМАЛЬНЫЙ СПОСОБ СЛИЯНИЯ ОТРЕЗКОВ ДАННЫХ (ВОЗМОЖНО, НЕРАВНЫХ) ДЛИН 
ПОЛУЧАЕТСЯ С ПОМОЩЬЮ ПОСТРОЕНИЯ ДЕРЕВА С МИНИМАЛЬНОЙ \emph{ВЗВЕШЕННОЙ} 
ДЛИНОЙ ПУТИ, ИСПОЛЬЗУЯ ДЛИНЫ ОТРЕЗКОВ В КАЧЕСТВЕ ВЕСОВ (СМ.~П.~2.3.4.5 
И~5.4.9), ЕСЛИ ПРЕНЕБРЕЧЬ ВРЕМЕНЕМ УСТАНОВКИ ЛЕНТ. нО ФАЙЛЫ, ЗАНИМАЮЩИЕ 
НЕСКОЛЬКО БОБИН, ВЕРОЯТНО, СЛЕДУЕТ ХРАНИТЬ НА ДИСКАХ ИЛИ ДРУГОМ 
ЗАПОМИНАЮЩЕМ УСТРОЙСТВЕ БОЛЬШОЙ ЕМКОСТИ, А НЕ НА ЛЕНТАХ.

13) в НАШЕМ ОБСУЖДЕНИИ МЫ, НЕ ЗАДУМЫВАЯСЬ, ПРЕДПОЛАГАЛИ, ЧТО ИМЕЕТСЯ 
ВОЗМОЖНОСТЬ ИСПОЛЬЗОВАТЬ НЕПОСРЕДСТВЕННО ИНСТРУКЦИИ ВВОДА/ВЫВОДА И ЧТО 
НИКАКОЙ СЛОЖНЫЙ СИСТЕМНЫЙ ИНТЕРФЕЙС НЕ МЕШАЕТ НАМ ИСПОЛЬЗОВАТЬ ЛЕНТЫ С 
ТАКОЙ ЭФФЕКТИВНОСТЬЮ, НА КАКУЮ РАССЧИТЫВАЛИ КОНСТРУКТОРЫ АППАРАТУРЫ. эТИ 
ИДЕАЛЬНЫЕ ПРЕДПОЛОЖЕНИЯ ПОЗВОЛИЛИ НАМ ПРОНИКНУТЬ В СУТЬ ПРОБЛЕМ СЛИЯНИЯ, 
И ОНИ МОГУТ ДАТЬ НЕКОТОРЫЙ ПОДХОД К КОНСТРУИРОВАНИЮ СООТВЕТСТВУЮЩИХ 
ОПЕРАЦИОННЫХ СИСТЕМ. оДНАКО СЛЕДУЕТ ПОНИМАТЬ, ЧТО МУЛЬТИПРОГРАММИРОВАНИЕ 
И МУЛЬТИПРОЦЕССИРОВАНИЕ МОГУТ ЗНАЧИТЕЛЬНО УСЛОЖНИТЬ СИТУАЦИЮ.

14) оБСУЖДАЕМЫЕ НАМИ ВОПРОСЫ БЫЛИ ВПЕРВЫЕ РАССМОТРЕНЫ В ПЕЧАТИ 
э.~X.~фРЭНДОМ [{\sl JACM,\/} {\bf 3} (1956), 134--165],у.~зОБЕРБЬЕРОМ 
[{\sl Electron. Datenverarb.,\/} {\bf 5} (1960), 28--44] И м.~а.~гОТЦЕМ 
[Digital Computer User's Handbook (New York, McGraw-Hill, 1967) 1.292--1.320].

\section рЕЗЮМЕ. мЫ МОЖЕМ СЛЕДУЮЩИМ ОБРАЗОМ ВКРАТЦЕ ВЫРАЗИТВ ВСЕ, ЧТО 
УЗНАЛИ О СРАВНЕНИИ РАЗЛИЧНЫХ СХЕМ СЛИЯНИЯ:

\proclaim тЕОРЕМА а. тРУДНО РЕШИТЬ, КАКАЯ СХЕМА СЛИЯНИЯ ЯВЛЯЕТСЯ 
НАИЛУЧШЕЙ В КОНКРЕТНОЙ СИТУАЦИИ. \endmark

пРИМЕРЫ, КОТОРЫЕ МЫ ВИДЕЛИ НА СХЕМЕ~а, ПОКАЗЫВАЮТ, КАК 100000~ЗАПИСЕЙ ПО 
100~ЛИТЕР (ИЛИ 1~МИЛЛИОН ЗАПИСЕЙ ПО 10~ЛИТЕР), РАСПОЛОЖЕННЫХ В СЛУЧАЙНОМ 
ПОРЯДКЕ, МОГЛИ БЫ БЫТЬ ОТСОРТИРОВАНЫ С ИСПОЛЬЗОВАНИЕМ ШЕСТИ ЛЕНТ ПРИ 
ДОСТАТОЧНО РЕАЛИСТИЧЕСКИХ ПРЕДПОЛОЖЕНИЯХ. эТИ ДАННЫЕ ЗАНИМАЮТ ОКОЛО 
ПОЛОВИНЫ ЛЕНТЫ И МОГУТ БЫТЬ ОТСОРТИРОВАНЫ ПРИБЛИЗИТЕЛЬНО ЗА 15--19 МИН;
ОДНАКО СУЩЕСТВУЮЩЕЕ ЛЕНТОЧНОЕ ОБОРУДОВАНИЕ СИЛЬНО РАЗЛИЧАЕТСЯ ПО 
ВОЗМОЖНОСТЯМ, И ВРЕМЯ ВЫПОЛНЕНИЯ ТАКОЙ РАБОТЫ НА РАЗНЫХ МАШИНАХ ИЗМЕНЯЕТСЯ 
В ДИАПАЗОНЕ ПРИБЛИЗИТЕЛЬНО ОТ~
%%405
ЧЕТЫРЕХ МИНУТ ДО~ДВУХ ЧАСОВ. в НАШИХ ПРИМЕРАХ ОКОЛО 3~МИН РАСХОДУЕТСЯ НА 
НАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ОТРЕЗКОВ И ВНУТРЕННЮЮ СОРТИРОВКУ, ОКОЛО 4.5~МИН---НА 
ОКОНЧАТЕЛЬНОЕ СЛИЯНИЕ И ПЕРЕМОТКУ ВЫВОДНОЙ ЛЕНТЫ И ОКОЛО 
7.5--11.5~МИН---НА ПРОМЕЖУТОЧНЫЕ СТАДИИ СЛИЯНИЯ.

еСЛИ ИМЕЕТСЯ ШЕСТЬ ЛЕНТ, КОТОРЫЕ НЕЛЬЗЯ ЧИТАТЬ В ОБРАТНОМ НАПРАВЛЕНИИ, ТО 
НАИЛУЧШИМ МЕТОДОМ СОРТИРОВКИ ПРИ НАШИХ ПРЕДПОЛОЖЕНИЯХ БЫЛО "МНОГОФАЗНОЕ 
СЛИЯНИЕ С РАСЩЕПЛЕНИЕМ ЛЕНТ" (ПРИМЕР~4), А ДЛЯ ЛЕНТ, ДОПУСКАЮЩИХ ОБРАТНОЕ 
ЧТЕНИЕ, НАИЛУЧШИМ МЕТОДОВ ОКАЗАЛСЯ МНОГОФАЗНЫЙ МЕТОД С ОБРАТНЫМ ЧТЕНИЕМ СО 
СЛОЖНЫМ РАЗМЕЩЕНИЕМ ФИКТИВНЫХ ОТРЕЗКОВ (ПРИМЕР~7). оСЦИЛЛИРУЮЩАЯ 
СОРТИРОВКА (ПРИМЕР~9) ЗАНИМАЕТ ВТОРОЕ МЕСТО. в ОБОИХ СЛУЧАЯХ КАСКАДНОЕ 
СЛИЯНИЕ БОЛЕЕ ПРОСТО И ЛИШЬ НЕЗНАЧИТЕЛЬНО МЕДЛЕННЕЕ (ПРИМЕРЫ~5 И~8). в 
СЛУЧАЕ ПРЯМОГО ЧТЕНИЯ ОБЫЧНОЕ СБАЛАНСИРОВАННОЕ СЛИЯНИЕ (ПРИМЕР~1) 
ОКАЗАЛОСЬ УДИВИТЕЛЬНО ЭФФЕКТИВНЫМ, ЧАСТИЧНО ИЗ-ЗА УДАЧИ В ЭТОМ 
КОНКРЕТНОМ ПРИМЕРЕ, А ЧАСТИЧНО ИЗ-ЗА ТОГО, ЧТО ОНО ТРАТИТ 
СРАВНИТЕЛЬНО МАЛО ВРЕМЕНИ НА ПЕРЕМОТКУ.

пОЛОЖЕНИЕ НЕСКОЛЬКО ИЗМЕНИЛОСЬ БЫ, ЕСЛИ БЫ В НАШЕМ РАСПОРЯЖЕНИИ БЫЛО 
ДРУГОЕ ЧИСЛО ЛЕНТ.

\section гЕНЕРАТОРЫ СОРТИРОВКИ. в УСЛОВИЯХ БОЛЬШОГО 
РАЗНООБРАЗИЯ ХАРАКТЕРИСТИК ДАННЫХ И ОБОРУДОВАНИЯ ПОЧТИ НЕВОЗМОЖНО 
НАПИСАТЬ ЕДИНСТВЕННУЮ ПРОГРАММУ ВНЕШНЕЙ СОРТИРОВКИ, КОТОРАЯ БЫЛА БЫ 
УДОВЛЕТВОРИТЕЛЬНОЙ В ПОДАВЛЯЮЩЕМ БОЛЬШИНСТВЕ СЛУЧАЕВ. тАКЖЕ ВЕСЬМА 
ТРУДНО СОЗДАТЬ ПРОГРАММУ, КОТОРАЯ В РЕАЛЬНЫХ УСЛОВИЯХ ЭФФЕКТИВНО 
РАБОТАЕТ С ЛЕНТАМИ. сЛЕДОВАТЕЛЬНО, ИЗГОТОВЛЕНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ 
СОРТИРОВКИ---САМОСТОЯТЕЛЬНАЯ ЗАДАЧА, ТРЕБУЮЩАЯ БОЛЬШОЙ РАБОТЫ. 
\dfn{гЕНЕРАТОР СОРТИРОВКИ}---ЭТО ПРОГРАММА, КОТОРАЯ, ОСНОВЫВАЯСЬ НА 
ПАРАМЕТРАХ, ОПИСЫВАЮЩИХ ФОРМАТ ДАННЫХ И КОНФИГУРАЦИЮ ОБОРУДОВАНИЯ,
 ПОРОЖДАЕТ МАШИННУЮ ПРОГРАММУ, СПЕЦИАЛЬНО ПРИСПОСОБЛЕННУЮ К КОНКРЕТНОМУ 
ПРИМЕНЕНИЮ СОРТИРОВКИ. пОДОБНАЯ ПРОГРАММА ЧАСТО СВЯЗАНА С ЯЗЫКАМИ ВЫСОКОГО 
УРОВНЯ, ТАКИМИ, КАК~кОБОЛ ИЛИ~PL/1, ИЛИ ОНА МОЖЕТ БЫТЬ НАПИСАНА КАК НАБОР 
МАКРООПРЕДЕЛЕНИЙ ДЛЯ ИСПОЛЬЗОВАНИЯ СОВМЕСТНО С МАКРОАССЕМБЛЕРОМ.

оДНОЙ ИЗ ОСОБЕННОСТЕЙ, ОБЫЧНО ОБЕСПЕЧИВАЕМЫХ ГЕНЕРАТОРОМ СОРТИРОВКИ, 
ЯВЛЯЕТСЯ ВОЗМОЖНОСТЬ ВСТАВЛЯТЬ "СОБСТВЕННЫЕ КОМАНДЫ"---ОСОБЫЕ ИНСТРУКЦИИ, 
КОТОРЫЕ ДОЛЖНЫ ВКЛЮЧАТЬСЯ В ПЕРВЫЙ И ПОСЛЕДНИЙ ПРОХОДЫ ПРОГРАММЫ 
СОРТИРОВКИ. сОБСТВЕННЫЕ КОМАНДЫ ПЕРВОГО ПРОХОДА ОБЫЧНО ИСПОЛЬЗУЮТСЯ, 
ЧТОБЫ ОТРЕДАКТИРОВАТЬ ИСХОДНЫЕ ЗАПИСИ, ЧАСТО СОКРАЩАЯ ИХ ИЛИ 
НЕЗНАЧИТЕЛЬНО УДЛИНЯЯ, ЧТОБЫ ПРИВЕСТИ ИХ К ФОРМЕ, БОЛЕЕ ПРОСТОЙ ДЛЯ 
СОРТИРОВКИ. пУСТЬ, НАПРИМЕР, ИСХОДНЫЕ ЗАПИСИ ДОЛЖНЫ БЫТЬ ОТСОРТИРОВАНЫ ПО 
ДЕВЯТИЛИТЕРНОМУ КЛЮЧУ, ИЗОБРАЖАЮЩЕМУ ДАТУ В ФОРМАТЕ МЕСЯЦ-ДЕНЬ-ГОД:
%%406
$$
|JUL04| \ |OCT311517| \ |NOV051605| \ |JUL141789| \ |NOV201917|
$$
тРЕХБУКВЕННЫЕ КОДЫ МЕСЯЦЕВ МОЖНО НАЙТИ В ТАБЛИЦЕ И ЗАМЕНИТЬ ЧИСЛАМИ, 
ПРИЧЕМ НАИБОЛЕЕ ЗНАЧАЩИЕ ПОЛЯ МОГУТ БЫТЬ ПОМЕЩЕНЫ СЛЕВА:
$$
|17760704| \ |15171031| \ |16051105| \ |17890714| \ |19171120|
$$
эТО УМЕНЬШАЕТ ДЛИНУ ЗАПИСЕЙ И ДЕЛАЕТ БОЛЕЕ ПРОСТЫМ ПОСЛЕДУЮЩЕЕ СРАВНЕНИЕ.
 (кОД КЛЮЧЕЙ МОГ БЫ БЫТЬ СДЕЛАН ДАЖЕ БОЛЕЕ КОМПАКТНЫМ.) сОБСТВЕННЫЕ 
КОМАНДЫ ПОСЛЕДНЕГО ПРОХОДА МОГУТ ИСПОЛЬЗОВАТЬСЯ ДЛЯ ВОССТАНОВЛЕНИЯ 
ИСХОДНОГО ФОРМАТА И/ИЛИ ДЛЯ ВНЕСЕНИЯ ДРУГИХ ЖЕЛАТЕЛЬНЫХ ИЗМЕНЕНИЙ В ФАЙЛ 
И/ИЛИ ДЛЯ ВЫЧИСЛЕНИЯ КАКОЙ-ЛИБО ФУНКЦИИ ОТ ВЫВОДНЫХ ЗАПИСЕЙ. аЛГОРИТМЫ 
СЛИЯНИЯ, КОТОРЫЕ МЫ ИЗУЧИЛИ, ОРГАНИЗОВАНЫ ТАКИМ ОБРАЗОМ, ЧТО ПОСЛЕДНИЙ 
ПРОХОД ЛЕГКО ОТЛИЧИТЬ ОТ ОСТАЛЬНЫХ ФАЗ СЛИЯНИЯ. зАМЕТИМ, ЧТО ЕСЛИ ИМЕЮТСЯ 
СОБСТВЕННЫЕ КОМАНДЫ, ТО ДОЛЖНО БЫТЬ ПО КРАЙНЕЙ МЕРЕ ДВА ПРОХОДА ПО ФАЙЛУ, 
ДАЖЕ ЕСЛИ ОН ПЕРВОНАЧАЛЬНО НАХОДИЛСЯ В ПОРЯДКЕ. сОБСТВЕННЫЕ КОМАНДЫ, 
ИЗМЕНЯЮЩИЕ РАЗМЕР ЗАПИСЕЙ, МОГУТ ЗАТРУДНИТЬ СОВМЕЩЕНИЕ НЕКОТОРЫХ 
ОПЕРАЦИЙ ВВОДА/ВЫВОДА В ОСЦИЛЛИРУЮЩЕЙ СОРТИРОВКЕ.

гЕНЕРАТОРЫ СОРТИРОВКИ ТАКЖЕ ЗАБОТЯТСЯ О СИСТЕМНЫХ ДЕТАЛЯХ, ТАКИХ, КАК 
СОГЛАШЕНИЯ О МЕТКАХ ЛЕНТ; ОНИ ТАКЖЕ ЧАСТО ОБЕСПЕЧИВАЮТ ПОДСЧЕТ 
КОНТРОЛЬНОЙ СУММЫ ИЛИ ИНЫЕ ПРОВЕРКИ ТОГО, ЧТО НИКАКАЯ ЧАСТЬ ФАЙЛА НЕ 
ПРОПАЛА И НЕ ИЗМЕНИЛАСЬ. иНОГДА ИМЕЮТСЯ СРЕДСТВА ДЛЯ ОСТАНОВКИ СОРТИРОВКИ 
В УДОБНЫХ МЕСТАХ И ВОЗОБНОВЛЕНИЯ ЕЕ ПОЗДНЕЕ. сАМЫЕ ВЫСОКОКАЧЕСТВЕННЫЕ 
ГЕНЕРАТОРЫ ПОЗВОЛЯЮТ ЗАПИСЯМ ИМЕТЬ ДИНАМИЧЕСКИ МЕНЯЮЩИЕСЯ ДЛИНЫ [СМ. 
D.~J.~Waks, {\sl CACM,\/} {\bf 6} (1963), 267--272].

\section *сЛИЯНИЕ С МЕНЬШИМ ЧИСЛОМ БУФЕРОВ. мЫ ВИДЕЛИ, ЧТО $2P+2$~БУФЕРОВ 
ДОСТАТОЧНО ДЛЯ ПОДДЕРЖАНИЯ БЫСТРОГО ДВИЖЕНИЯ ЛЕНТ В ТЕЧЕНИЕ 
$P\hbox{-ПУТЕВОГО}$ СЛИЯНИЯ. в ЗАВЕРШЕНИЕ ЭТОГО ПУНКТА ПРОВЕДЕМ 
МАТЕМАТИЧЕСКИЙ АНАЛИЗ ВРЕМЕНИ СЛИЯНИЯ В ТОМ СЛУЧАЕ, КОГДА ИМЕЕТСЯ МЕНЬШЕ 
$2P+2$~БУФЕРОВ.

оЧЕВИДНО, ЧТО ЖЕЛАТЕЛЬНЫ ДВА БУФЕРА ВЫВОДА, ТАК КАК МЫ СМОЖЕМ ЗАПИСЫВАТЬ 
ИЗ ОДНОГО БУФЕРА, ОБРАЗУЯ В ЭТО ЖЕ ВРЕМЯ СЛЕДУЮЩИЙ БЛОК ВЫВОДА В ДРУГОМ. 
пОЭТОМУ МЫ МОЖЕМ ВООБЩЕ НЕ РАССМАТРИВАТЬ ВОПРОС ВЫВОДА И ЗАНЯТЬСЯ ТОЛЬКО 
ВВОДОМ.

дОПУСТИМ, ИМЕЕТСЯ $P+Q$~БУФЕРОВ ВВОДА, ГДЕ $1\le Q\le P$. вОСПОЛЬЗУЕМСЯ 
ДЛЯ ОПИСАНИЯ НАШЕЙ СИТУАЦИИ МОДЕЛЬЮ, ПРЕДЛОЖЕННОЙ л.~дЖ.~вУДРАМОМ [{\sl 
IBM Systems J.,\/} {\bf 9} (1970), 118--144]. чТЕНИЕ ОДНОГО БЛОКА ЛЕНТЫ 
ЗАНИМАЕТ ОДНУ ЕДИНИЦУ ВРЕМЕНИ. иМЕЕТСЯ ВЕРОЯТНОСТЬ~$p_0$ ТОГО, ЧТО В 
ТЕЧЕНИЕ ЭТОГО ВРЕМЕНИ НИ ОДИН ИЗ БУФЕРОВ ВВОДА НЕ СТАНЕТ ПУСТЫМ, $p_1$---ЧТО 
ОДИН БУФЕР СТАНЕТ ПУСТЫМ, $p{\ge 2}$---ЧТО ДВА ИЛИ БОЛЬШЕ БУФЕРОВ СТАНУТ 
%%407
ПУСТЫМИ И~Т.~Д. пО ЗАВЕРШЕНИИ ЧТЕНИЯ ЛЕНТЫ МЫ ОКАЗЫВАЕМСЯ В ОДНОМ 
ИЗ $Q+1$~СОСТОЯНИЙ:

\medskip
{\sl сОСТОЯНИЕ~$0$:\/} $Q$~БУФЕРОВ  ПУСТЫ. мЫ НАЧИНАЕМ ЧИТАТЬ 
БЛОК ПОДХОДЯЩЕГО ФАЙЛА В ОДИН ИЗ НИХ, ИСПОЛЬЗУЯ МЕТОД ПРОГНОЗИРОВАНИЯ, 
ОПИСАННЫЙ РАНЕЕ В ЭТОМ ПУНКТЕ. чЕРЕЗ ОДНУ ЕДИНИЦУ ВРЕМЕНИ МЫ ПЕРЕХОДИМ В 
СОСТОЯНИЕ~$1$ С ВЕРОЯТНОСТЬЮ~$p_0$, В ПРОТИВНОМ СЛУЧАЕ МЫ ОСТАЕМСЯ В 
СОСТОЯНИИ~$0$.

{\sl сОСТОЯНИЕ~$1$:\/} $Q-1$~БУФЕРОВ ПУСТЫ. мЫ НАЧИНАЕМ ЧИТАТЬ В ОДИН ИЗ 
НИХ, ПРЕДСКАЗЫВАЯ ПОДХОДЯЩИЙ ФАЙЛ. чЕРЕЗ ОДНУ ЕДИНИЦУ ВРЕМЕНИ МЫ ПЕРЕХОДИМ 
В СОСТОЯНИЕ~$2$ С ВЕРОЯТНОСТЬЮ~$p_0$, В СОСТОЯНИЕ~$1$ С ВЕРОЯТНОСТЬЮ~$p_1$ 
И В СОСТОЯНИЕ~$0$ С ВЕРОЯТНОСТЬЮ~$p_{\ge2}$.

$\vdots$

{\sl сОСТОЯНИЕ~$Q-1$:\/} ОДИН БУФЕР ПУСТ. мЫ НАЧИНАЕМ ЧИТАТЬ В НЕГО, 
ПРЕДСКАЗЫВАЯ ПОДХОДЯЩИЙ ФАЙЛ. чЕРЕЗ ОДНУ ЕДИНИЦУ ВРЕМЕНИ МЫ ПЕРЕХОДИМ В 
СОСТОЯНИЕ~$Q$ С ВЕРОЯТНОСТЬЮ~$p_0$, В СОСТОЯНИЕ~$Q-1$ С 
ВЕРОЯТНОСТЬЮ~$p_1$,~\dots, В СОСТОЯНИЕ~$1$ С ВЕРОЯТНОСТЬЮ~$P_{Q-1}$, И В 
СОСТОЯНИЕ~$0$ С ВЕРОЯТНОСТЬЮ~$p_{\ge Q}$.

{\sl сОСТОЯНИЕ~$Q$:\/} ВСЕ БУФЕРЫ ЗАПОЛНЕНЫ. чТЕНИЕ ЛЕНТ ОСТАНАВЛИВАЕТСЯ 
В СРЕДНЕМ НА $\mu$~ЕДИНИЦ ВРЕМЕНИ, И ЗАТЕМ МЫ ПЕРЕХОДИМ В СОСТОЯНИЕ~$1$.
\medskip

мЫ НАЧИНАЕМ С СОСТОЯНИЯ~$0$. эТА МОДЕЛЬ СИТУАЦИИ СООТВЕТСТВУЕТ 
МАРКОВСКОМУ ПРОЦЕССУ (СМ.~УПР.~2.3.4.2-26), КОТОРЫЙ МОЖНО ПРОАНАЛИЗИРОВАТЬ 
С ПОМОЩЬЮ ПРОИЗВОДЯЩИХ ФУНКЦИЙ СЛЕДУЮЩИМ ИНТЕРЕСНЫМ СПОСОБОМ. пУСТЬ 
$z$---ПРОИЗВОЛЬНЫЙ ПАРАМЕТР, И ПРЕДПОЛОЖИМ, ЧТО КАЖДЫЙ РАЗ, КОГДА МЫ 
РЕШИЛИ ЧИТАТЬ С ЛЕНТЫ, ДЕЛАЕМ ЭТО С ВЕРОЯТНОСТЬЮ~$z$, А С 
ВЕРОЯТНОСТЬЮ~$1-z$ ЗАВЕРШАЕМ АЛГОРИТМ. пУСТЬ $g_Q(z)=\sum_{n\ge0} 
a_n^{(Q)}z^n(1-z)$ БУДЕТ СРЕДНИМ ЧИСЛОМ ПОЯВЛЕНИЙ В ЭТОМ ПРОЦЕССЕ 
СОСТОЯНИЯ~$Q$; ОТСЮДА СЛЕДУЕТ, ЧТО  $a_n^{(Q)}$---ЭТО СРЕДНЕЕ ЧИСЛО 
ПОЯВЛЕНИЙ СОСТОЯНИЯ~$Q$, ЕСЛИ БЫЛО ПРОЧИТАНО РОВНО $n$~БЛОКОВ. тОГДА 
$n+a_n\mu$---СРЕДНЕЕ СУММАРНОЕ ВРЕМЯ, ЗАТРАЧЕННОЕ НА ВВОД И ВЫЧИСЛЕНИЯ. еСЛИ 
БЫ ИМЕЛОСЬ ПОЛНОЕ СОВМЕЩЕНИЕ, КАК В АЛГОРИТМЕ С $(2P+2)$~БУФЕРАМИ, 
ТО СУММАРНОЕ ВРЕМЯ ВКЛЮЧАЛО БЫ ТОЛЬКО $n$~ЕДИНИЦ, ТАК ЧТО 
$a_n\mu$~ПРЕДСТАВЛЯЕТ ВРЕМЯ ЗАДЕРЖКИ ЧТЕНИЯ.

пУСТЬ $A_{ij}$---ВЕРОЯТНОСТЬ ТОГО, ЧТО МЫ ПЕРЕХОДИМ ИЗ СОСТОЯНИЯ~$i$ В 
СОСТОЯНИЕ~$j$ В ЭТОМ ПРОЦЕССЕ ПРИ~$0\le i$, $j\le Q+1$, ГДЕ $Q+1$---НОВОЕ 
СОСТОЯНИЕ "ОСТАНОВКИ". нАПРИМЕР, ДЛЯ $Q=1$, $2$, $3$ МАТРИЦЫ~$A$ БУДУТ 
СЛЕДУЮЩИМИ:
%%407
$$
\eqalign{
Q&=1:\pmatrix{
p_{\ge1}z & p_0z & 1-z\cr
1 & 0 & 0\cr
0 & 0 & 0\cr
},\cr
Q&=2:\pmatrix{
p_{\ge1}z & p_0z & 0 & 1-z\cr
p_{\ge2}z & p_1z & p_0z& 1-z\cr
0 & 1 & 0 & 0 \cr
0 & 0 & 0 & 0\cr
},\cr
Q&=3:\pmatrix{
p_{\ge1}z & p_0z & 0 & 0 & 1-z\cr
p_{\ge2}z & p_1z & p_0z& 0 & 1-z\cr
p_{\ge3}z & p_2z & p_1z& p_0z & 1-z\cr
0 & 0 & 1 & 0 & 0\cr
0 & 0 & 0& 0 & 0 \cr
}.\cr
}
$$
иЗ УПР.~2.3.4.2-26b ИМЕЕМ, ЧТО 
$g_Q(z) =\hbox{ АЛГЕБРАИЧЕСКОЕ ДОПОЛНЕНИЕ $Q_0$}  (I-A)/\det (I-A)$. тАК, 
НАПРИМЕР, ЕСЛИ $Q=1$, ИМЕЕМ
$$
\eqalign{
g_1(z)&=\det\pmatrix{
0 & -p_0z & z-1\cr
1 & 0 & 0 \cr
0 & 0 & 1\cr
}/
\det\pmatrix{
1-p_{\ge1}z & -p_0z & z-1\cr
-1 & 1 & 0\cr
0& 0 & 1\cr
}=\cr
&={p_0z\over 1-p_1z-p_0z}={p_0z\over1-z}=\sum_{n\ge0} np_0z^n(1-z),\cr
}
$$
ТАК ЧТО $a_n^{(1)}=np_0$. эТО, КОНЕЧНО, ОЧЕВИДНО ЗАРАНЕЕ, ТАК КАК 
ПРИ $Q=1$ ЗАДАЧА ОЧЕНЬ ПРОСТА. аНАЛОГИЧНОЕ ВЫЧИСЛЕНИЕ ДЛЯ 
$Q=2$ (СМ.~УПР.~14) ДАЕТ МЕНЕЕ ОЧЕВИДНУЮ ФОРМУЛУ:
$$
a_n^{(2)}={p_0^2n\over 1-p_1}-{p_0^2(1-p_1^n)\over(1-p_1)^2}.
\eqno(10)
$$
в ОБЩЕМ СЛУЧАЕ МОЖНО ПОКАЗАТЬ, ЧТО $a_n^{(Q)}$ ИМЕЕТ 
ВИД~$\alpha^{(Q)}n+O(1)$ ПРИ $n\to\infty$, ГДЕ КОНСТАНТУ~$\alpha^{(Q)}$ 
НЕ СЛИШКОМ ТРУДНО ВЫЧИСЛИТЬ. (сМ. УПР.~15.) кАК ОКАЗЫВАЕТСЯ, $\alpha^{(3)}=p_0^3/((1-p_1)^2-p_0p_2)$.

иСХОДЯ ИЗ ПРИРОДЫ СЛИЯНИЯ, ДОВОЛЬНО РАЗУМНО ПРЕДПОЛОЖИТЬ, ЧТО $\mu=1/P$ И 
ЧТО ВЕРОЯТНОСТИ~$p_k$ СООТВЕТСТВУЮТ БИНОМИАЛЬНОМУ РАСПРЕДЕЛЕНИЮ
$$
p_k=\perm{P}{k}\perm{1}{P}^k{\left({P-1\over P}\right)\hbox to 0pt{.\hss}}^{P-k}
$$
нАПРИМЕР, ЕСЛИ $P=5$, ТО $p_0= .32768$, $p_1=.4096$, $p_2= .2048$, 
$p_3=.0512$, $p_4=.0064$ И~$p_5=.00032$; СЛЕДОВАТЕЛЬНО, $\alpha^{(1)}=0.328$, 
$\alpha^{(2)}=0.182$ И~$\alpha^{(3)}=0.127$. дРУГИМИ СЛОВАМИ, ЕСЛИ МЫ 
ИСПОЛЬЗУЕМ $5+3$~ВВОДНЫХ БУФЕРОВ ВМЕСТО~$5+5$, ТО МОЖНО ОЖИДАТЬ 
ДОПОЛНИТЕЛЬНОГО ВРЕМЕНИ  ЗАДЕРЖКИ ЧТЕНИЯ ПОРЯДКА~$0.127/5\approx 2.5\%$.

%% 409

кОНЕЧНО, ЭТА МОДЕЛЬ---ТОЛЬКО ОЧЕНЬ ГРУБОЕ ПРИБЛИЖЕНИЕ. мЫ ЗНАЕМ, ЧТО ПРИ 
$Q=P$ ВООБЩЕ НЕТ ВРЕМЕНИ ЗАДЕРЖКИ, НО ЕСЛИ СУДИТЬ ПО МОДЕЛИ, ТО ЕСТЬ. 
дОПОЛНИТЕЛЬНОЕ ВРЕМЯ ЗАДЕРЖКИ ЧТЕНИЯ ДЛЯ МЕНЬШИХ~$Q$ ПОЧТИ ТОЧНО 
УРАВНОВЕШИВАЕТ ВЫИГРЫШ В НАКЛАДНЫХ РАСХОДАХ, ПОЛУЧАЕМЫЙ ОТ ИСПОЛЬЗОВАНИЯ 
БОЛЕЕ КРУПНЫХ БЛОКОВ, ТАК ЧТО ПРОСТАЯ СХЕМА С $Q=P$ КАЖЕТСЯ ОПРАВДАННОЙ.
\excercises

\ex[13] вЫВЕДИТЕ ФОРМУЛУ ДЛЯ ТОЧНОГО ЧИСЛА ЛИТЕР НА ЛЕНТЕ, ЕСЛИ КАЖДЫЙ 
БЛОК СОДЕРЖИТ $n$~ЛИТЕР. сЧИТАЙТЕ, ЧТО ЛЕНТА МОГЛА БЫ ВМЕСТИТЬ 
РОВНО 23000000 ЛИТЕР, ЕСЛИ БЫ НЕ БЫЛО МЕЖБЛОЧНЫХ ПРОМЕЖУТКОВ.

\ex[15] оБЎЯСНИТЕ, ПОЧЕМУ ПЕРВЫЙ БУФЕР ФАЙЛА~$2$ В СТРОКЕ~$6$ РИС.~84 
СОВСЕМ ПУСТ.

\ex[20] бУДЕТ ЛИ АЛГОРИТМ~F РАБОТАТЬ ДОЛЖНЫМ ОБРАЗОМ, ЕСЛИ ВМЕСТО 
$2P$~БУФЕРОВ ВВОДА ИМЕЕТСЯ ТОЛЬКО $2P-1$? еСЛИ ДА, ДОКАЖИТЕ ЭТО, ЕСЛИ 
НЕТ--- ПРИВЕДИТЕ ПРИМЕР, КОГДА АЛГОРИТМ ТЕРПИТ НЕУДАЧУ.

\ex[20] кАК ИЗМЕНИТЬ АЛГОРИТМ~F, ЧТОБЫ ОН РАБОТАЛ ТАКЖЕ И ПРИ~$P=1$?

\rex[21] еСЛИ В РАЗЛИЧНЫХ ФАЙЛАХ ИМЕЮТСЯ РАВНЫЕ КЛЮЧИ, НЕОБХОДИМО В 
ПРОЦЕССЕ ПРОГНОЗИРОВАНИЯ ДЕЙСТВОВАТЬ ОЧЕНЬ АККУРАТНО. оБЎЯСНИТЕ, ПОЧЕМУ, И 
ПОКАЖИТЕ, КАК ИЗБЕЖАТЬ ТРУДНОСТЕЙ, ЕСЛИ БОЛЕЕ СТРОГО ОПРЕДЕЛИТЬ 
ОПЕРАЦИИ СЛИЯНИЯ И ПРОГНОЗИРОВАНИЯ В АЛГОРИТМЕ~F.

\ex[22] кАКИЕ ИЗМЕНЕНИЯ СЛЕДУЕТ СДЕЛАТЬ В АЛГОРИТМЕ~5.4.3с, ЧТОБЫ 
ПРЕОБРАЗОВАТЬ ЕГО В АЛГОРИТМ КАСКАДНОГО СЛИЯНИЯ \emph{С СОВМЕЩЕНИЕМ 
ПЕРЕМОТКИ} НА  $T+1$~ЛЕНТАХ?

\rex [26] нАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ В ПРИМЕРЕ~7 СХЕМЫ~а ПОРОЖДАЕТ
$$
(A_1D_1)^{11}\quad D_1(A_1D_1)^{10}\quad D_1(A_1D_1)^9\quad D_1(A_1D_1)^7
$$
НА ЛЕНТАХ~1--4, ГДЕ $(A_1D_1)^7$ ОЗНАЧАЕТ 
$A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1$. пОКАЖИТЕ, КАК ВСТАВИТЬ 
ДОПОЛНИТЕЛЬНЫЕ ОТРЕЗКИ~$A_0$ И~$D_0$ НАИЛУЧШИМ ИЗ ВОЗМОЖНЫХ СПОСОБОВ (В 
ТОМ СМЫСЛЕ, ЧТО ОБЩЕЕ ЧИСЛО ОБРАБАТЫВАЕМЫХ ВО ВРЕМЯ СЛИЯНИЯ НАЧАЛЬНЫХ 
ОТРЕЗКОВ БУДЕТ МИНИМАЛЬНЫМ), ЧТОБЫ ПРИВЕСТИ РАСПРЕДЕЛЕНИЕ К
$$
A(DA)^{14}\quad  (DA)^{28}\quad  (DA)^{26}\quad  (DA)^{22}.
$$
[\emph{уКАЗАНИЕ.} чТОБЫ СОХРАНИТЬ ЧЕТНОСТЬ, НЕОБХОДИМО ВСТАВЛЯТЬ~$A_0$ 
И~$D_0$ В ВИДЕ СОСЕДНИХ ПАР. чИСЛА СЛИЯНИЯ ДЛЯ КАЖДОГО НАЧАЛЬНОГО ОТРЕЗКА 
МОГУТ БЫТЬ ПОДСЧИТАНЫ, КАК В УПР~5.4.4-5; ЗДЕСЬ ПОЯВЛЯЕТСЯ НЕКОТОРОЕ 
УПРОЩЕНИЕ, ТАК КАК СОСЕДНИЕ ОТРЕЗКИ ВСЕГДА ИМЕЮТ СОСЕДНИЕ ЧИСЛА СЛИЯНИЯ.]

\ex[20] иЗ СХЕМЫ~а ВИДНО, ЧТО БОЛЬШИНСТВО СХЕМ НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ 
ОТРЕЗКОВ (ЗА ИСКЛЮЧЕНИЕМ НАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ ДЛЯ КАСКАДНОГО СЛИЯНИЯ) 
ИМЕЕТ ТЕНДЕНЦИЮ ПОМЕЩАТЬ ПОСЛЕДОВАТЕЛЬНЫЕ ОТРЕЗКИ НА РАЗЛИЧНЫЕ ЛЕНТЫ. еСЛИ 
БЫ ПОСЛЕДОВАТЕЛЬНЫЕ ОТРЕЗКИ ПОПАЛИ НА ОДНУ ЛЕНТУ, ТО МЫ МОГЛИ БЫ 
СЭКОНОМИТЬ СТАРТСТОПНОЕ ВРЕМЯ; МОЖНО ЛИ ПОЭТОМУ СЧИТАТЬ ХОРОШЕЙ 
МЫСЛЬ ИЗМЕНИТЬ АЛГОРИТМЫ РАСПРЕДЕЛЕНИЯ ТАК, ЧТОБЫ ОНИ РЕЖЕ ПЕРЕКЛЮЧАЛИ ЛЕНТЫ?

\rex[22] оЦЕНИТЕ, СКОЛЬКО ВРЕМЕНИ ЗАНЯЛ БЫ МНОГОФАЗНЫЙ АЛГОРИТМ С ОБРАТНЫМ 
ЧТЕНИЕМ ИЗ СХЕМЫ~а, ЕСЛИ БЫ МЫ ИСПОЛЬЗОВАЛИ ДЛЯ СОРТИРОВКИ ВСЕ $T=6$ ЛЕНТ, 
А НЕ $T=5$, КАК В ПРИМЕРЕ~7. бЫЛО ЛИ РАЗУМНО ИЗБЕГАТЬ ИСПОЛЬЗОВАНИЯ 
ВВОДНОЙ ЛЕНТЫ?

\ex[м23] иСПОЛЬЗУЯ АНАЛИЗ, ПРОВЕДЕННЫЙ В П.~5.4.2 И~5.4.3, ПОКАЖИТЕ, ЧТО 
ДЛИНА КАЖДОЙ ПЕРЕМОТКИ ВО ВРЕМЯ СТАНДАРТНОГО МНОГОФАЗНОГО СЛИЯНИЯ С ШЕСТЬЮ 
ЛЕНТАМИ ИЛИ КАСКАДНОГО СЛИЯНИЯ РЕДКО ПРЕВЫШАЕТ 54\% ФАЙЛА (ИСКЛЮЧАЯ 
НАЧАЛЬНУЮ И КОНЕЧНУЮ ПЕРЕМОТКИ, КОТОРЫЕ ОХВАТЫВАЮТ ВЕСЬ ФАЙЛ).

%%410
\ex[23] иЗМЕНИВ ПОДХОДЯЩИЕ ЭЛЕМЕНТЫ ТАБЛ.~1, ОЦЕНИТЕ, СКОЛЬКО 
ВРЕМЕНИ ЗАНЯЛИ БЫ ПЕРВЫЕ ДЕВЯТЬ ПРИМЕРОВ СХЕМЫ~а, ЕСЛИ БЫ МЫ ИМЕЛИ 
ДВУХСКОРОСТИУЮ ПЕРЕМОТКУ (БЫСТРУЮ И МЕДЛЕННУЮ) сЧИТАЙТЕ, ЧТО $p=1$, ЕСЛИ 
ЛЕНТА ЗАПОЛНЕНА МЕНЬШЕ ЧЕМ НА ОДНУ ЧЕТВЕРТЬ, А ДЛЯ БОЛЕЕ ЗАПОЛНЕННОЙ 
ЛЕНТЫ ВРЕМЯ ПЕРЕМОТКИ РАВНО ПРИБЛИЗИТЕЛЬНО ПЯТИ СЕКУНДАМ ПЛЮС ТО ВРЕМЯ, 
КОТОРОЕ ПОЛУЧИЛОСЬ БЫ ПРИ $\rho=1/5$ иЗМЕНИТЕ ПРИМЕР~8 ТАК, ЧТОБЫ ОН 
ИСПОЛЬЗОВАЛ КАСКАДНОЕ СЛИЯНИЕ С КОПИРОВАНИЕМ, ПОСКОЛЬКУ ПЕРЕМЕТКА И 
ПРЯМОЕ ЧТЕНИЕ В ЭТОМ СЛУЧАЕ МЕДЛЕННЕЕ КОПИРОВАНИЯ [\emph{уКАЗАНИЕ:} 
ИСПОЛЬЗУЙТЕ РЕЗУЛЬТАТ УПР. 10 ]

\ex[40] рАССМОТРИМ РАЗБИЕНИЕ ШЕСТИ ЛЕНТ НА ТРИ ПАРЫ ЛЕНТ, ГДЕ КАЖДАЯ ПАРА 
ИГРАЕТ РОЛЬ ОДНОЙ ЛЕНТЫ В МНОГОФАЗНОМ СЛИЯНИИ С~$T=3$ оДНА ЛЕНТА КАЖДОЙ 
ПАРЫ БУДЕТ СОДЕРЖАТЬ БЛОКИ~$1$, $3$, $5$,~\dots, А ДРУГАЯ---БЛОКИ~$2$, $4$, 
$6$,~\dots, ТАКИМ СПОСОБОМ МЫ, ПО СУЩЕСТВУ, ДОБИВАЕМСЯ ТОГО, ЧТОБЫ ВО ВСЕ 
ВРЕМЯ СЛИЯНИЯ ДВЕ ВВОДНЫЕ И ДВЕ ВЫВОДНЫЕ ЛЕНТЫ ОСТАВАЛИСЬ АКТИВНЫМИ, 
ПРИЧЕМ ЭФФЕКТИВНАЯ СКОРОСТЬ СЛИЯНИЯ УДВАИВАЕТСЯ

\item{(a)} нАЙДИТЕ ПОДХОДЯЩИЙ СПОСОБ РАСПРОСТРАНИТЬ АЛГОРИТМ~F НА ЭТОТ СЛУЧАЙ.

\item{(b)} оЦЕНИТЕ ОБЩЕЕ ВРЕМЯ ВЫПОЛНЕНИЯ, КОТОРОЕ ПОЛУЧИЛОСЬ БЫ, ЕСЛИ БЫ 
ЭТОТ МЕТОД БЫЛ ИСПОЛЬЗОВАН ДЛЯ СОРТИРОВКИ 100000~ЗАПИСЕЙ ПО 100~ЛИТЕР, 
РАССМОТРЕВ СЛУЧАЙ КАК ПРЯМОГО, ТАК И ОБРАТНОГО ЧТЕНИЯ.

\ex[20] мОЖЕТ ЛИ ОСЦИЛЛИРУЮЩАЯ СОРТИРОВКА С ПЯТЬЮ ЛЕНТАМИ, В ТОМ ВИДЕ КАК 
ОНА ОПРЕДЕЛЕНА В АЛГОРИТМЕ 5.4.5в, ИСПОЛЬЗОВАТЬСЯ ДЛЯ СОРТИРОВКИ ЧЕТЫРЕХ 
ПОЛНЫХ БОБИН ИСХОДНЫХ ДАННЫХ ДО МОМЕНТА ОКОНЧАТЕЛЬНОГО СЛИЯНИЯ?

\ex[м19] вЫВЕДИТЕ (10).

\ex[вм29] дОКАЖИТЕ, ЧТО $g_Q(z)=h_Q(z)/(1-z)$, ГДЕ $h_Q(z)$~ЯВЛЯЕТСЯ 
РАЦИОНАЛЬНОЙ ФУНКЦИЕЙ~$z$,  НЕ ИМЕЮЩЕЙ ОСОБЕННОСТЕЙ ВНУТРИ ЕДИНИЧНОГО КРУГА;
СЛЕДОВАТЕЛЬНО, $a_n^{(Q)}=h_Q(1)n+O(1)$ ПРИ $n\to\infty$. в ЧАСТНОСТИ, 
ПОКАЖИТЕ, ЧТО
$$
h_3(1)=\det\pmatrix{
0 & -p_0 & 0 & 0 \cr
0 & 1-p_1 & -p_0 & 0 \cr
0 & -p_2 & 1-p_1 & -p_0 \cr
1 & 0 & 0 & 0 \cr
}
/\det\pmatrix{
1 & -p_0 & 0 & 0 \cr
1 & 1-p_1 & -p_0 & 0 \cr
1 & -p_2 & 1-p_1 & -p_0\cr
0 & 0 & -1 & 1 \cr
}.
$$
\ex[M46] пРОАНАЛИЗИРУЙТЕ СЛИЯНИЕ С $P+Q$~БУФЕРАМИ БОЛЕЕ ТЩАТЕЛЬНО, ЧЕМ ЭТО 
БЫЛО СДЕЛАНО В ТЕКСТЕ, ИСПОЛЬЗУЯ БОЛЕЕ ТОЧНУЮ МОДЕЛЬ.

\ex[41] пРОВЕДИТЕ ДЕТАЛЬНОЕ ИЗУЧЕНИЕ ЗАДАЧИ СОРТИРОВКИ 100000~ЗАПИСЕЙ ЯО 
100~ЛИТЕР, НАРИСУЙТЕ СХЕМЫ, ПОДОБНЫЕ СХЕМЕ~а, В ПРЕДПОЛОЖЕНИИ, 
ЧТО ИМЕЕТСЯ~3, 4 ИЛИ~5 ЛЕНТ

\subsubchap{*вНЕШНЯЯ ПОРАЗРЯДНАЯ СОРТИРОВКА} %5.4.7
в ПРЕДЫДУЩИХ ПУНКТАХ МЫ РАССМОТРЕЛИ ПРОЦЕСС ЛЕНТОЧНОЙ   СОРТИРОВКИ 
СЛИЯНИЕМ; НО СУЩЕСТВУЕТ И ДРУГОЙ СПОСОБ СОРТИРОВКИ НА ЛЕНТАХ, ОСНОВАННЫЙ 
НА ПРИНЦИПЕ ПОРАЗРЯДНОЙ СОРТИРОВКИ, ИСПОЛЬЗУЕМОЙ В МЕХАНИЧЕСКИХ 
СОРТИРОВАЛЬНЫХ МАШИНАХ ДЛЯ ПЕРФОКАРТ (СР. С П.~5.2.5). эТОТ МЕТОД ИНОГДА 
НАЗЫВАЮТ РАСПРЕДЕЛЯЮЩЕЙ СОРТИРОВКОЙ, ПОКОЛОННОЙ СОРТИРОВКОЙ, 
КАРМАННОЙ СОРТИРОВКОЙ, ЦИФРОВОЙ СОРТИРОВКОЙ, СОРТИРОВКОЙ РАЗДЕЛЕНИЕМ И Т. 
Д. оН, КАК ОКАЗЫВАЕТСЯ, ПО СУЩЕСТВУ, \emph{ПРОТИВОПОЛОЖЕН} СЛИЯНИЮ!

пРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО В НАШЕМ РАСПОРЯЖЕНИИ ИМЕЮТСЯ ЧЕТЫРЕ ЛЕНТЫ, А 
КЛЮЧЕЙ МОЖЕТ БЫТЬ ТОЛЬКО ВОСЕМЬ: $0$, $1$, $2$, $3$, 
%%411
$4$, $5$, $6$, $7$. еСЛИ ИСХОДНЫЕ ДАННЫЕ НАХОДЯТСЯ НА ЛЕНТЕ~$T1$, 
ТО НАЧНЕМ С ПЕРЕПИСИ ВСЕХ ЧЕТНЫХ КЛЮЧЕЙ НА~$T3$ И ВСЕХ НЕЧЕТНЫХ НА~$T4$:
\ctable{
\hfill#&&\bskip\hfill$#$\hfill\bskip\cr
 & T1 & T2 & T3 & T4 \cr
дАНО    & \{0, 1, 2, 3, 4, 5, 6, 7\} & - & - & - \cr
пРОХОД 1& - & - & \{0, 2, 4, 6\} & \{1, 3, 5, 7\}\cr
\noalign{
\noindent тЕПЕРЬ ПЕРЕМАТЫВАЕМ ЛЕНТЫ И ЧИТАЕМ~$T3$, А ЗАТЕМ ~$T4$, ПОМЕЩАЯ 
$\{0, 1, 4, 5\}$ НА~$T1$ И~$\{2,  3,  6,  7\}$ НА~$T2$:
}
пРОХОД 2. &  \{0,4\} \{1,5\}  &     \{2,6\} \{3,7\} & - &- \cr
\noalign{
\noindent(сТРОКА~$\{0, 4\}\{1, 5\}$ ОБОЗНАЧАЕТ ФАЙЛ, СОДЕРЖАЩИЙ ЗАПИСИ 
ТОЛЬКО С КЛЮЧАМИ~$0$ И~$4$, ЗА КОТОРЫМИ СЛЕДУЮТ ЗАПИСИ ТОЛЬКО С 
КЛЮЧАМИ~$1$ И~$5$. зАМЕТИМ, ЧТО~$T1$ ТЕПЕРЬ СОДЕРЖИТ ТЕ КЛЮЧИ, СРЕДНИЙ 
ДВОИЧНЫЙ РАЗРЯД КОТОРЫХ СОДЕРЖИТ~$0$.) пОСЛЕ ЕЩЕ ОДНОЙ ПЕРЕМОТКИ И 
РАСПРЕДЕЛЕНИЯ КЛЮЧЕЙ~$0$, $1$, $2$, $3$ НА~$T3$ И КЛЮЧЕЙ~$4$, $5$, $6$, 
$7$ НА~$T4$ МЫ ИМЕЕМ
}
пРОХОД~3 & - & & \{0\}\{1\}\{2\}\{3\} &  \{4\} \{5\} \{6\} \{7\} \cr
}
тЕПЕРЬ КОПИРОВАНИЕ~$T4$ В КОНЕЦ~$T3$ ЗАВЕРШАЕТ РАБОТУ. в ОБЩЕМ СЛУЧАЕ ДЛЯ 
КЛЮЧЕЙ В ДИАПАЗОНЕ ОТ~$0$ ДО~$2^k-1$ МОЖНО ОТСОРТИРОВАТЬ ФАЙЛ 
АНАЛОГИЧНЫМ ОБРАЗОМ, ИСПОЛЬЗОВАВ $k$~ПРОХОДОВ, ЗА КОТОРЫМИ СЛЕДУЕТ ФАЗА 
ОКОНЧАТЕЛЬНОЙ "СБОРКИ", КОПИРУЮЩАЯ ПРИМЕРНО ПОЛОВИНУ ДАННЫХ С ОДНОЙ ЛЕНТЫ 
НА ДРУГУЮ. иМЕЯ ШЕСТЬ ЛЕНТ, МЫ МОЖЕМ АНАЛОГИЧНЫМ ОБРАЗОМ ИСПОЛЬЗОВАТЬ 
ПРЕДСТАВЛЕНИЯ ПО ОСНОВАНИЮ~$3$ ДЛЯ СОРТИРОВКИ КЛЮЧЕЙ ОТ~$0$ ДО~$3^k-1$ ЗА $k$~ПРОХОДОВ.

иСПОЛЬЗУЮТСЯ ТАКЖЕ МЕТОДЫ С ЧАСТИЧНЫМИ ПРОХОДАМИ. пРЕДПОЛОЖИМ, НАПРИМЕР, 
ЧТО ДОПУСКАЕТСЯ ДЕСЯТЬ КЛЮЧЕЙ 
$\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$, И РАССМОТРИМ СЛЕДУЮЩУЮ ПРОЦЕДУРУ, 
ПРИНАДЛЕЖАЩУЮ р.~л.~эШЕНХЕРСТУ [{\sl Theory of Switching,\/} {\bf 7} 
(Harvard Univ. Comp. Laboratory: May, 1954), I.1--I.76]:
\ctable{
\hfill#
&\bskip\hfill$#$\hfill\bskip
&\bskip\hfill$#$\hfill\bskip
&\bskip\hfill$#$\hfill\bskip
&\bskip\hfill$#$\hfill\bskip
&\bskip#\hfill\cr
 & T1 & T2 & T3 & T4 \cr
дАНО    & \{0, 1,~\ldots, 9\} & - & - & - \cr
пРОХОД~1.& - & \{0, 2, 4, 7\} & \{1, 5, 6\} & \{3, 8, 9\} & $1.0$~ПРОХОД \cr
пРОХОД~2.& \{0\} & - & \{1, 5, 6\}\{2,7\} & \{3,8,9\}\{4\} &$0.4$~ПРОХОДА\cr
пРОХОД~3.& \{0\}\{1\}\{2\} & \{6\}\{7\} & - & \{3,8,9\}\{4\}\{5\}& $0.5$~ПРОХОДА\cr
пРОХОД~4. & \{0\}\{1\}\{2\}\{3\} & \{6\}\{7\}\{8\} & \{9\} &\{4\}\{5\}& $0.3$~ПРОХОДА\cr
сБОРКА & \{0\}\{1\}\{2\}\{3\}\{4\}\ldots\{9\} & & & & $0.6$~ПРОХОДА\cr
& & & & & $\overline{\hbox{$2.8$ ПРОХОДА}}$\cr
}

%%412

еСЛИ КАЖДОЕ ЗНАЧЕНИЕ КЛЮЧА ВСТРЕЧАЕТСЯ ПРИМЕРНО В ОДНОЙ ДЕСЯТОЙ СЛУЧАЕВ, 
ТО ЭТА ПРОЦЕДУРА ДЛЯ СОРТИРОВКИ ДЕСЯТИ КЛЮЧЕЙ ЗАТРАЧИВАЕТ ТОЛЬКО 
$2.8$~ПРОХОДА, В ТО ВРЕМЯ КАК ПЕРВЫЙ ПРИМЕР ТРЕБУЕТ $3.5$~ПРОХОДА ДЛЯ 
СОРТИРОВКИ ВСЕГО ВОСЬМИ КЛЮЧЕЙ. тАКИМ ОБРАЗОМ, МЫ ВИДИМ, ЧТО ИСКУСНАЯ 
СХЕМА РАСПРЕДЕЛЕНИЯ МОЖЕТ ВЫЗВАТЬ ЗНАЧИТЕЛЬНОЕ РАЗЛИЧИЕ ДЛЯ 
ПОРАЗРЯДНОЙ СОРТИРОВКИ ТОЧНО ТАК ЖЕ, КАК ДЛЯ СЛИЯНИЯ.

сХЕМЫ РАСПРЕДЕЛЕНИЯ ПРЕДЫДУЩИХ ПРИМЕРОВ ПРЕДСТАВИМ, КАК И ОБЫЧНО, 
ДРЕВОВИДНЫМИ СТРУКТУРАМИ:
\picture{РИС. НА СТР. 412}
кРУГЛЫЕ ВНУТРЕННИЕ УЗЛЫ ЭТИХ ДЕРЕВЬЕВ ЗАНУМЕРОВАНЫ~$1$, $2$, $3$,~\dots В 
СООТВЕТСТВИИ С ШАГАМИ ПРОЦЕССА~$1$, $2$, $3$,~\dots. иМЕНА ЛЕНТ~$A$, $B$, 
$C$, $D$ (ВМЕСТО $T1$, $T2$, $T3$, $T4$) ПОМЕЩЕНЫ РЯДОМ С РЕБРАМИ ДЕРЕВА, 
ЧТОБЫ УКАЗАТЬ, КУДА ПОПАДАЮТ ЗАПИСИ. кВАДРАТНЫЕ ВНЕШНИЕ УЗЛЫ ИЗОБРАЖАЮТ 
ЧАСТИ ФАЙЛА, СОДЕРЖАЩИЕ ТОЛЬКО ОДИН КЛЮЧ, И ЭТОТ КЛЮЧ ИЗОБРАЖЕН ЖИРНЫМ 
ШРИФТОМ ПОД СООТВЕТСТВУЮЩИМ УЗЛОМ. рЕБРА НАД КВАДРАТНЫМИ УЗЛАМИ ВСЕ 
ПОМЕЧЕНЫ ИМЕНЕМ ВЫВОДНОЙ ЛЕНТЫ ($C$ В ПЕРВОМ ПРИМЕРЕ, $A$ ВО ВТОРОМ).

тАКИМ ОБРАЗОМ, ШАГ~3 ПРИМЕРА~1 СОСТОИТ ИЗ ЧТЕНИЯ С ЛЕНТЫ~$D$ И ЗАПИСИ 
КЛЮЧЕЙ~$1$ И~$5$ НА ЛЕНТУ~$A$ И КЛЮЧЕЙ~$3$ И~$7$ НА ЛЕНТУ~$B$. нЕТРУДНО 
ВИДЕТЬ, ЧТО ЧИСЛО ВЫПОЛНЯЕМЫХ ПРОХОДОВ РАВНО \emph{ДЛИНЕ ВНЕШНЕГО ПУТИ} 
ДЕРЕВА, ДЕЛЕННОЙ НА ЧИСЛО ВНЕШНИХ УЗЛОВ, ЕСЛИ МЫ ПРИНИМАЕМ, ЧТО ВСЕ КЛЮЧИ 
РАВНОВЕРОЯТНЫ.

в СИЛУ ПОСЛЕДОВАТЕЛЬНОЙ ПРИРОДЫ ЛЕНТЫ И ДИСЦИПЛИНЫ "ПЕРВЫМ 
ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ", КОТОРОЙ ПОДЧИНЯЕТСЯ ПРЯМОЕ ЧТЕНИЕ, 
НЕЛЬЗЯ ВЗЯТЬ ЗА ОСНОВУ СХЕМЫ РАСПРЕДЕЛЕНИЯ \emph{ЛЮБОЕ} ПОМЕЧЕННОЕ ДЕРЕВО. 
в ДЕРЕВЕ ПРИМЕРА~1 ДАННЫЕ ЗАПИСЫВАЮТСЯ НА ЛЕНТУ~$A$ НА ШАГЕ~2 И ШАГЕ~3; 
ДАННЫЕ, ЗАПИСАННЫЕ В ТЕЧЕНИЕ ШАГА~2, НЕОБХОДИМО ИСПОЛЬЗОВАТЬ РАНЬШЕ ДАННЫХ,
 ЗАПИСАННЫХ В ТЕЧЕНИЕ ШАГА~3. в ОБЩЕМ СЛУЧАЕ, ЕСЛИ МЫ ЗАПИСЫВАЕМ НА 
ЛЕНТУ В ТЕЧЕНИЕ ШАГОВ~$i$ И~$j$, ГДЕ $i < j$, ПЕРВЫМИ СЛЕДУЕТ
%%413
ИСПОЛЬЗОВАТЬ ДАННЫЕ, ЗАПИСАННЫЕ В ТЕЧЕНИЕ ШАГА~$i$; ЕСЛИ ДЕРЕВО 
СОДЕРЖИТ ДВЕ ВЕТВИ ВИДА
\picture{РИС. СТР. 413}
ТО ДОЛЖНО ВЫПОЛНЯТЬСЯ УСЛОВИЕ $k<l$. кРОМЕ ТОГО, МЫ НЕ МОЖЕМ НИЧЕГО 
ЗАПИСЫВАТЬ НА ЛЕНТУ~$A$ \emph{МЕЖДУ} ШАГАМИ~$k$ И~$l$, ПОСКОЛЬКУ МЕЖДУ 
ЧТЕНИЕМ И ЗАПИСЬЮ НЕОБХОДИМА ПЕРЕМОТКА.

тЕ ЧИТАТЕЛИ, КОТОРЫЕ ПРОРАБОТАЛИ УПРАЖНЕНИЯ П.~5.4.4, НЕМЕДЛЕННО ПОЙМУТ, 
ЧТО ДОПУСТИМЫЕ ДЕРЕВЬЯ ДЛЯ ПОРАЗРЯДНОЙ СОРТИРОВКИ С ПРЯМЫМ ЧТЕНИЕМ НА 
$T$~ЛЕНТАХ---ЭТО В ТОЧНОСТИ "СИЛЬНЫЕ $T\hbox{-fifo}$" ДЕРЕВЬЯ, ОПИСЫВАЮЩИЕ 
СОРТИРОВКУ \emph{СЛИЯНИЕМ} НА $T$~ЛЕНТАХ С ПРЯМЫМ ЧТЕНИЕМ! (сМ. 
УПР.~5.4.4-20.) еДИНСТВЕННОЕ РАЗЛИЧИЕ ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО ВСЕ ВНЕШНИЕ 
УЗЛЫ РАССМАТРИВАЕМЫХ ЗДЕСЬ ДЕРЕВЬЕВ ПОМЕЧЕНЫ ОДНОЙ И ТОЙ ЖЕ ЛЕНТОЙ. мЫ 
МОГЛИ БЫ СНЯТЬ ЭТО ОГРАНИЧЕНИЕ, ПРЕДПОЛОЖИВ, ЧТО СУЩЕСТВУЕТ 
ОКОНЧАТЕЛЬНАЯ ФАЗА "СБОРКИ", ПЕРЕНОСЯЩАЯ ВСЕ ЗАПИСИ НА ВЫВОДНУЮ ЛЕНТУ, ИЛИ 
МОГЛИ БЫ ДОБАВИТЬ ЭТО ОГРАНИЧЕНИЕ К ПРАВИЛАМ ДЛЯ $T\hbox{-fifo}$ ДЕРЕВЬЕВ, 
ПОТРЕБОВАВ, ЧТОБЫ НАЧАЛЬНЫЙ РАСПРЕДЕЛИТЕЛЬНЫЙ ПРОХОД СОРТИРОВКИ СЛИЯНИЕМ 
БЫЛ ЯВНО ВЫРАЖЕН В СООТВЕТСТВУЮЩЕМ ДЕРЕВЕ СЛИЯНИЯ.

иНЫМИ СЛОВАМИ, \emph{КАЖДОЙ СХЕМЕ СЛИЯНИЯ СООТВЕТСТВУЕТ 
СХЕМА РАСПРЕДЕЛЕНИЯ И КАЖДОЙ СХЕМЕ РАСПРЕДЕЛЕНИЯ СООТВЕТСТВУЕТ СХЕМА 
СЛИЯНИЯ.} пО НЕКОТОРОМ РАЗМЫШЛЕНИИ ЭТО СТАНОВИТСЯ ПОНЯТНЫМ. рАССМОТРИМ 
СОРТИРОВКУ СЛИЯНИЕМ, ДЕЛАЮЩУЮ ВСЕ НАОБОРОТ, Т.~Е.~"РАЗЛИВАЮЩУЮ" 
ОКОНЧАТЕЛЬНЫЙ ВЫВОДНОЙ ФАЙЛ В ПОДФАЙЛЫ, КОТОРЫЕ "РАЗЛИВАЮТСЯ" В ДРУГИЕ, 
И~Т.Д.; НАКОНЕЦ, МЫ РАЗОЛЬЕМ ФАЙЛ В $S$~ОТРЕЗКОВ. пОДОБНАЯ СХЕМА 
ВОЗМОЖНА С ЛЕНТАМИ ТОГДА И ТОЛЬКО ТОГДА, КОГДА ВОЗМОЖНА СООТВЕТСТВУЮЩАЯ 
СХЕМА РАСПРЕДЕЛЕНИЯ ДЛЯ ПОРАЗРЯДНОЙ СОРТИРОВКА $S$~КЛЮЧЕЙ. эТА 
ДВОЙСТВЕННОСТЬ СЛИЯНИЯ И РАСПРЕДЕЛЕНИЯ ПОЧТИ ТОЧНА;
ОНА НЕ ВЫПОЛНЯЕТСЯ ТОЛЬКО В ОДНОМ ОТНОШЕНИИ: ВВОДНАЯ ЛЕНТА ДОЛЖНА 
СОХРАНЯТЬСЯ В РАЗНЫЕ МОМЕНТЫ ВРЕМЕНИ.

пРИМЕР С ВОСЕМЬЮ КЛЮЧАМИ, РАССМОТРЕННЫЙ В НАЧАЛЕ ЭТОГО ПУНКТА, ОЧЕВИДНО, 
ДВОЙСТВЕН СБАЛАНСИРОВАННОМУ СЛИЯНИЮ НА ЧЕТЫРЕХ ЛЕНТАХ. пРИМЕР С ДЕСЯТЬЮ 
КЛЮЧАМИ И ЧАСТИЧНЫМИ ПРОХОДАМИ СООТВЕТСТВУЕТ СЛЕДУЮЩЕЙ СХЕМЕ СЛИЯНИЯ 
ДЕСЯТИ ОТРЕЗКОВ (ЕСЛИ МЫ СКРОЕМ ФАЗЫ КОПИРОВАНИЯ---ШАГИ 6--11 В ДЕРЕВЕ):
\ctable{
#\hfill&&\bskip\hfill$#$\hfill\bskip\cr
 & T1 & T2 & T3 & T4 \cr
нАЧАЛЬНОЕ РАСПРЕДЕЛЕНИЕ &   1^4 & 1^3 & 1^1 & 1^2 \cr
шАГ ДЕРЕВА 5 & 1^3 & 1^2 & - & 1^2 3^1 \cr
%%414
шАГ ДЕРЕВА 4 & 1^2 &  1^1 &  2^1 & 1^23^1 \cr
шАГ ДЕРЕВА 3 & 1^1 & - &  2^13^1 & 1^13^1 \cr
шАГ ДЕРЕВА 2 &  -  & 4^1 & 3^1 & 3^1 \cr
шАГ ДЕРЕВА 1 &  10^1& - & - & - \cr
}
еСЛИ СРАВНИТЬ ЕЕ С ПОРАЗРЯДНОЙ СОРТИРОВКОЙ, ТО-ВИДНО, ЧТО ОБА МЕТОДА ИМЕЮТ,
 В СУЩНОСТИ, ОДНУ И ТУ ЖЕ СТРУКТУРУ, НО ОБРАТНЫ ВО ВРЕМЕНИ И ИМЕЮТ 
ОБРАТНОЕ РАСПОЛОЖЕНИЕ СОДЕРЖИМОГО НА ЛЕНТАХ: $1^23^1$ (ДВА ОТРЕЗКА 
ДЛИНЫ~1 КАЖДЫЙ, ЗА КОТОРЫМИ НАХОДИТСЯ ОДИН ОТРЕЗОК ДЛИНЫ~3) 
СООТВЕТСТВУЕТ 
$\{3, 8, 9\}{4} {5}$ (ДВА ПОДФАЙЛА, СОДЕРЖАЩИЕ КАЖДЫЙ ПО 1~КЛЮЧУ, 
ПЕРЕД КОТОРЫМИ РАСПОЛОЖЕН ОДИН ПОДФАЙЛ, СОДЕРЖАЩИЙ 3~КЛЮЧА).

дВИГАЯСЬ В ДРУГУЮ СТОРОНУ, МЫ МОЖЕМ В ПРИНЦИПЕ ПОСТРОИТЬ ПОРАЗРЯДНУЮ 
СОРТИРОВКУ, ДВОЙСТВЕННУЮ МНОГОФАЗНОМУ СЛИЯНИЮ, КАСКАДНОМУ СЛИЯНИЮ И Т. Д. 
нАПРИМЕР, МНОГОФАЗНОМУ СЛИЯНИЮ 21~ОТРЕЗКА НА ТРЕХ ЛЕНТАХ, ИЗОБРАЖЕННОМУ В 
НАЧАЛЕ П.~5.4.2, СООТВЕТСТВУЕТ СЛЕДУЮЩАЯ ИНТЕРЕСНАЯ ПОРАЗРЯДНАЯ СОРТИРОВКА:
\ctable{
\sevenrm#\hfill&&\bskip\hfill$\scriptstyle#$\hfill\cr
 & T1 & T2 & T3 \cr
дАНО & \{0, 1, \ldots, 20\} & - & - \cr
пРОХОД 1& - & \{0, 2, 4, 5, 7, 9, 10, 12, 13, 15, 17, 18, 20\} & \{1, 3, 6,
 8, 11, 14, 16, 19\}\cr
пРОХОД 2 & \{0, 5, 10, 13, 18\} & - & \{1, 3, 6, 8, 11, 14, 16, 19\}\{2, 4,
 7, 9, 12, 15, 17, 20\}\cr
пРОХОД 3 & \{0, 5, 10, 13, 18\} \{1, 6, 11, 14, 19\} \{2, 7, 12, 15, 20\} 
& \{3, 8, 16\} \{4, 9, 17\} & - \cr
пРОХОД 4 & - & \{3, 8, 16\}\{4, 9, 17\} \{5, 10, 18\}\{6, 11, 19\}\{7, 12, 
20\} & \{0, 13\}\{1, 14\}\{2,15\}\cr
пРОХОД 5 & \{8\}\{9\}\{10\}\{11\}\{12\} & - & \{0, 13\}\{1,14\}\{2, 
15\}\{3,16\}\ldots\{7,20\}\cr
пРОХОД 6 & \{8\} \{9\} \{10\} \{11\} \{12\} \{13\}\ldots\{20\} & \{0\} 
\{1\} \ldots \{7\} & - \cr
}
пРАВИЛО РАСПРЕДЕЛЕНИЯ, СОГЛАСНО КОТОРОМУ КЛЮЧИ РАСПОЛАГАЮТСЯ НА ЛЕНТАХ НА 
КАЖДОМ ШАГЕ, КАЖЕТСЯ МАГИЧЕСКИМ, НО НА САМОМ ДЕЛЕ ОНО ИМЕЕТ ПРОСТУЮ сВЯЗЬ 
С СИСТЕМОЙ СЧИСЛЕНИЯ, ИСПОЛЬЗУЮЩЕЙ ЧИСЛА фИБОНАЧЧИ! (сМ. УПР.~2.)

\section оБРАТНОЕ ЧТЕНИЕ. дВОЙСТВЕННОСТЬ ПОРАЗРЯДНОЙ СОРТИРОВКИ И СЛИЯНИЯ 
ПРИМЕНИМА ТАКЖЕ И К АЛГОРИТМАМ, ЧИТАЮЩИМ ЛЕНТУ В ОБРАТНОМ НАПРАВЛЕНИИ. мЫ 
ОПРЕДЕЛИЛИ "$T\hbox{-lifo}$ ДЕРЕВЬЯ" В П.~5.4.4, И НЕТРУДНО ВИДЕТЬ, ЧТО 
ОНИ ПОДХОДЯТ ДЛЯ ПОРАЗРЯДНОЙ СОРТИРОВКИ В ТОЙ ЖЕ МЕРЕ, ЧТО И ДЛЯ 
СОРТИРОВКИ СЛИЯНИЕМ.

пОРАЗРЯДНАЯ СОРТИРОВКА С ОБРАТНЫМ ЧТЕНИЕМ БЫЛА ФАКТИЧЕСКИ РАССМОТРЕНА 
дЖОНОМ мОЧЛИ ЕЩЕ В 1946~Г. В ОДНОЙ ИЗ ПЕРВЫХ ОПУБЛИКОВАННЫХ РАБОТ ПО 
СОРТИРОВКЕ ВООБЩЕ (СМ. \S~5.5);
мОЧЛИ НА САМОМ ДЕЛЕ ДАЛ СЛЕДУЮЩУЮ КОНСТРУКЦИЮ:
\ctable{
#\hfill&&\bskip\hfill$#$\hfill\bskip\cr
 & T1 & T2 & T3 & T4\cr
дАНО & - & \{0, 1, \ldots, 9\} & - & - \cr
пРОХОД 1& \{4, 5\} & - & \{2, 3, 6, 7\} & \{0, 1, 8, 9\}\cr
пРОХОД 2&\{4, 5\} \{2, 7\} & \{3, 6\} & - & \{0, 1, 8, 9\}\cr
пРОХОД 3&\{4,5\} \{2, 7\} \{0,9\} & \{3, 6\} \{1,8\}& - & - \cr
пРОХОД 4& \{4, 5\} \{2, 7\} & \{3, 6\} \{1, 8\} & \{9\} & \{0\}\cr
\hfill\dots \cr
пРОХОД  8 & - & - & \{9\}\{8\}\{7\}\{6\}\{5\} & \{0\}\{1\}\{2\}\{3\}\{4\}\cr
оКОНЧАТЕЛЬНАЯ СБОРКА & - & - & \{0\} \{1\}\{2\}\{3\}\{4\}\{5\}\ldots\{9\}\cr
}
%%415
\bye