\input style

эТА СХЕМА НЕ ЯВЛЯЕТСЯ НАИБОЛЕЕ ЭФФЕКТИВНОЙ СРЕДИ ВСЕХ ВОЗМОЖНЫХ, НО ОНА 
ИНТЕРЕСНА ТЕМ, ЧТО ПОКАЗЫВАЕТ, ЧТО МЕТОДЫ С ЧАСТИЧНЫМИ ПРОХОДАМИ 
РАССМАТРИВАЛИСЬ ДЛЯ ПОРАЗРЯДНОЙ СОРТИРОВКИ ЕЩЕ В 1946~Г., ХОТЯ В 
ЛИТЕРАТУРЕ ПО СЛИЯНИЮ ОНИ ПОЯВИЛИСЬ ЛИШЬ ОКОЛО 1960~Г.

эФФЕКТИВНАЯ КОНСТРУКЦИЯ СХЕМ РАСПРЕДЕЛЕНИЯ С ОБРАТНЫМ ЧТЕНИЕМ БЫЛА 
ПРЕДЛОЖЕНА э.~бАЙЕСОМ 
[{\sl CACM\/}, {\bf 11} (1968), 491--493]. пУСТЬ ДАНО $P+1$ ЛЕНТ И $S$ 
КЛЮЧЕЙ; РАЗДЕЛИТЕ КЛЮЧИ НА $P$ ПОДФАЙЛОВ, КАЖДЫЙ ИЗ КОТОРЫХ СОДЕРЖИТ 
$\lfloor S/P \rfloor$ ИЛИ $\lceil S/P \rceil$ КЛЮЧЕЙ, И ПРИМЕНЯЙТЕ ЭТУ 
ПРОЦЕДУРУ РЕКУРСИВНО К КАЖДОМУ ПОДФАЙЛУ. еСЛИ $S<2P$, ТО ОДИН ПОДФАЙЛ 
ДОЛЖЕН СОСТОЯТЬ ИЗ ЕДИНСТВЕННОГО НАИМЕНЬШЕГО КЛЮЧА; ЕГО И СЛЕДУЕТ ЗАПИСАТЬ 
НА ВЫВОДНУЮ ЛЕНТУ. (оБЩАЯ КОНСТРУКЦИЯ С ПРЯМЫМ ПОРЯДКОМ р.~м.~кАРПА, 
ОПИСАННАЯ В КОНЦЕ П.~5.4.4, ВКЛЮЧАЕТ ЭТОТ МЕТОД КАК ЧАСТНЫЙ СЛУЧАЙ.)

оБРАТНОЕ ЧТЕНИЕ НЕСКОЛЬКО УСЛОЖНЯЕТ СЛИЯНИЕ, ПОСКОЛЬКУ ОНИ ОБРАЩАЕТ 
ПОРЯДОК ОТРЕЗКОВ. сООТВЕТСТВУЮЩИЙ ЭФФЕКТ ИМЕЕТСЯ И В ПОРАЗРЯДНОЙ 
СОРТИРОВКЕ. рЕЗУЛЬТАТ ОКАЗЫВАЕТСЯ УСТОЙЧИВЫМ ИЛИ "АНТИУСТОЙЧИВЫМ" В 
ЗАВИСИМОСТИ ОТ ТОГО, КАКОЙ УРОВЕНЬ ДОСТИГНУТ В ДЕРЕВЕ. пОСЛЕ ПОРАЗРЯДНОЙ 
СОРТИРОВКИ С ОБРАТНЫМ ЧТЕНИЕМ, КОГДА НЕКОТОРЫЕ ВНЕШНИЕ УЗЛЫ НАХОДЯТСЯ НА 
ЧЕТНЫХ УРОВНЯХ, А НЕКОТОРЫЕ---НА НЕЧЕТНЫХ, ДЛЯ ОДНИХ КЛЮЧЕЙ ОТНОСИТЕЛЬНЫЙ 
ПОРЯДОК РАЗЛИЧНЫХ ЗАПИСЕЙ С ОДИНАКОВЫМИ КЛЮЧАМИ БУДЕТ \emph{СОВПАДАТЬ} С 
ПЕРВОНАЧАЛЬНЫМ ПОРЯДКОМ, НО ДЛЯ ДРУГИХ ОН БУДЕТ \emph{ПРОТИВОПОЛОЖЕН} 
ИСХОДНОМУ. (сР. С УПР.~6.)

\emph{оСЦИЛЛИРУЮЩАЯ} СОРТИРОВКА СЛИЯНИЕМ ТАКЖЕ ИМЕЕТ СВОЮ ПАРУ В ЭТОЙ 
ДВОЙСТВЕННОСТИ. в \emph{ОСЦИЛЛИРУЮЩЕЙ ПОРАЗРЯДНОЙ СОРТИРОВКЕ} МЫ 
ПРОДОЛЖАЕМ РАЗДЕЛЯТЬ КЛЮЧИ, ПОКА НЕ ДОСТИГНЕМ ПОД- ФАЙЛОВ, СОДЕРЖАЩИХ 
ТОЛЬКО ОДИН КЛЮЧ ИЛИ ДОСТАТОЧНО МАЛЫХ, ЧТОБЫ ПОДДАВАТЬСЯ ВНУТРЕННЕЙ 
СОРТИРОВКЕ; ТАКИЕ ПОДФАЙЛЫ СОРТИРУЮТСЯ И ЗАПИСЫВАЮТСЯ НА ВЫВОДНУЮ ЛЕНТУ, 
ЗАТЕМ ПРОЦЕСС РАЗДЕЛЕНИЯ ВОЗОБНОВЛЯЕТСЯ. нАПРИМЕР, ЕСЛИ ИМЕЮТСЯ ТРИ 
РАБОЧИЕ ЛЕНТЫ И ОДНА ВЫВОДНАЯ И ЕСЛИ КЛЮЧИ ЯВЛЯЮТСЯ ДВОИЧНЫМИ ЧИСЛАМИ, 
МЫ МОЖЕМ НАЧАТЬ С ТОГО, .ЧТО ПОМЕСТИМ КЛЮЧИ ВИДА `$0x$' НА ЛЕНТУ T1, А 
КЛЮЧИ `$1x$' НА ЛЕНТУ T2. еСЛИ НА ЛЕНТЕ T1 ОКАЖЕТСЯ БОЛЬШЕ ЗАПИСЕЙ, ЧЕМ 
ЕМКОСТЬ ПАМЯТИ, ТО ВНОВЬ ПРОСМАТРИВАЕМ ЕЕ И ПОМЕЩАЕТ `$00x$' НА T2 И 
`$01x$' НА Tз. тЕПЕРЬ, ЕСЛИ ПОДФАЙЛ `$00x$' ДОСТАТОЧНО КОРОТКИЙ, 
ПРОИЗВОДИМ ВНУТРЕННЮЮ СОРТИРОВКУ ЕГО И ВЫВОДИМ РЕЗУЛЬТАТ, А ЗАТЕМ 
НАЧИНАЕМ ОБРАБОТКУ ПОДФАЙЛА `$01x$'. пОДОБНЫЙ МЕТОД БЫЛ 
НАЗВАН э.~X.~фРЭНДОМ "КАСКАДНОЙ ПСЕВДОПОРАЗРЯДНОЙ СОРТИРОВКОЙ" [{\sl 
JACM\/}, {\bf 3} (1956), 157--159]; БОЛЕЕ ПОДРОБНО ЕГО 
РАЗРАБОТАЛИ X.~нЭГЛЕР [{\sl JACM\/}, {\bf 6} (1959), 459--468], КОТОРЫЙ 
ДАЛ ЕМУ КРАСОЧНОЕ ИМЯ "МЕТОД ДВУГЛАВОГО ЗМИЯ", И к. X. гОДЕТТ 
[{\sl IBM Tech. Disclosure Bull.\/}, {\bf 12} (April, 1970), 1849--1853].

%% 416
\qsection пРЕВОСХОДИТ ЛИ ПОРАЗРЯДНАЯ СОРТИРОВКА СЛИЯНИЕ? оДНИМ ВАЖНЫМ 
СЛЕДСТВИЕМ ПРИНЦИПА ДВОЙСТВЕННОСТИ ЯВЛЯЕТСЯ ТО, ЧТО 
\emph{ПОРАЗРЯДНАЯ СОРТИРОВКА ОБЫЧНО ХУЖЕ СОРТИРОВКИ СЛИЯНИЕМ}. 
эТО СВЯЗАНО С ТЕМ, ЧТО МЕТОД 
ВЫБОРА С ЗАМЕЩЕНИЕМ ДАЕТ СОРТИРОВКЕ СЛИЯНИЕМ ОПРЕДЕЛЕННОЕ ПРЕИМУЩЕСТВО: 
НЕТ ОЧЕВИДНОГО ПУТИ ТАК ПОСТРОИТЬ ПОРАЗРЯДНУЮ СОРТИРОВКУ, ЧТОБЫ МОЖНО БЫЛО 
ИСПОЛЬЗОВАТЬ ВНУТРЕННИЕ СОРТИРОВКИ, ВКЛЮЧАЮЩИЕ БОЛЕЕ ОДНОЙ ЕМКОСТИ 
ПАМЯТИ ЗА ОДИН РАЗ. нА САМОМ ДЕЛЕ ОСЦИЛЛИРУЮЩАЯ ПОРАЗРЯДНАЯ СОРТИРОВКА 
ЧАСТО БУДЕТ ПОРОЖДАТЬ ПОДФАЙЛЫ, НЕСКОЛЬКО МЕНЬШИЕ ЕМКОСТИ ПАМЯТИ, ТАК 
ЧТО ЕЕ СХЕМА РАСПРЕДЕЛЕНИЯ СООТВЕТСТВУЕТ ДЕРЕВУ СО ЗНАЧИТЕЛЬНО БОЛЬШИМ 
ЧИСЛОМ ВНЕШНИХ УЗЛОВ, ЧЕМ БЫЛО БЫ ПРИ ИСПОЛЬЗОВАНИИ СЛИЯНИЯ И ВЫБОРА С 
ЗАМЕЩЕНИЕМ. сООТВЕТСТВЕННО ВОЗРАСТАЕТ ДЛИНА ВНЕШНЕГО ПУТИ ДЕРЕВА (Т. Е.
 ВРЕМЯ СОРТИРОВКИ). (сМ. УПР. 5.3.1--33.)

дЛЯ ВНЕШНЕЙ ПОРАЗРЯДНОЙ СОРТИРОВКИ СУЩЕСТВУЕТ, ОДНАКО, ОДНО ВАЖНОЕ 
ПРИМЕНЕНИЕ. пРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО ИМЕЕТСЯ ФАЙЛ, СОДЕРЖАЩИЙ ФАМИЛИИ 
ВСЕХ СОТРУДНИКОВ БОЛЬШОГО ПРЕДПРИЯТИЯ В АЛФАВИТНОМ ПОРЯДКЕ; ПРЕДПРИЯТИЕ 
СОСТОИТ ИЗ 10 ОТДЕЛЕНИЙ, И ТРЕБУЕТСЯ ОТСОРТИРОВАТЬ ЭТОТ ФАЙЛ ПО 
ОТДЕЛЕНИЯМ, \emph{СОХРАНЯЯ} АЛФАВИТНЫЙ ПОРЯДОК СОТРУДНИКОВ В КАЖДОМ 
ОТДЕЛЕНИИ. еСЛИ ФАЙЛ ДЛИННЫЙ, ТО МЫ ИМЕЕМ ДЕЛО ИМЕННОЕ ТОЙ СИТУАЦИЕЙ, 
ГДЕ СЛЕДУЕТ ПРИМЕНЯТЬ СТАБИЛЬНУЮ ПОРАЗРЯДНУЮ СОРТИРОВКУ, ТАК КАК ЧИСЛО 
ЗАПИСЕЙ, ПРИНАДЛЕЖАЩИХ КАЖДОМУ ИЗ 10 ОТДЕЛЕНИЙ, БУДЕТ, ВЕРОЯТНО, БОЛЬШЕ, 
ЧЕМ ЧИСЛО ЗАПИСЕЙ, КОТОРОЕ БЫЛО БЫ В НАЧАЛЬНЫХ ОТРЕЗКАХ, ПОЛУЧЕННЫХ 
ВЫБОРОМ С ЗАМЕЩЕНИЕМ. вООБЩЕ ГОВОРЯ, ЕСЛИ ДИАПАЗОН КЛЮЧЕЙ ТАК МАЛ, ЧТО 
НАБОР ЗАПИСЕЙ С ОДИНАКОВЫМИ КЛЮЧАМИ БОЛЕЕ ЧЕМ ВДВОЕ ПРЕВЫСИТ 
ОПЕРАТИВНУЮ ПАМЯТЬ, ТО РАЗУМНО ИСПОЛЬЗОВАТЬ ПОРАЗРЯДНУЮ СОРТИРОВКУ.

мЫ ВИДЕЛИ В П.~5.2.5, ЧТО НА НЕКОТОРЫХ ВЫСОКОСКОРОСТНЫХ эвм 
\emph{ВНУТРЕННЯЯ} ПОРАЗРЯДНАЯ СОРТИРОВКА ПРЕДПОЧТИТЕЛЬНЕЕ СЛИЯНИЯ, 
ПОСКОЛЬКУ "ВНУТРЕННИЙ ЦИКЛ" ПОРАЗРЯДНОЙ СОРТИРОВКИ ОБХОДИТСЯ БЕЗ СЛОЖНЫХ 
ПЕРЕХОДОВ. еСЛИ ВНЕШНЯЯ ПАМЯТЬ ОЧЕНЬ БЫСТРАЯ, ТО ДЛЯ ТАКИХ МАШИН МОЖЕТ 
ОКАЗАТЬСЯ ПРОБЛЕМОЙ ПРОВОДИТЬ СЛИЯНИЕ ДАННЫХ С ТАКОЙ СКОРОСТЬЮ, 
ЧТОБЫ УСПЕТЬ ЗА ОБОРУДОВАНИЕМ ВВОДА/ВЫВОДА. пОЭТОМУ В ПОДОБНОЙ СИТУАЦИИ 
ПОРАЗРЯДНАЯ СОРТИРОВКА, ВОЗМОЖНО, ЛУЧШЕ СЛИЯНИЯ, ОСОБЕННО ЕСЛИ ИЗВЕСТНО, 
ЧТО КЛЮЧИ РАВНОМЕРНО РАСПРЕДЕЛЕНЫ.

\excercises
\ex[20] бЛИЖЕ К НАЧАЛУ П. 5.4 БЫЛО ОПРЕДЕЛЕНО ОБЩЕЕ 
СБАЛАНСИРОВАННОЕ СЛИЯНИЕ НА $T$ ЛЕНТАХ С ПАРАМЕТРОМ $P$, $1 \le P < T$. 
пОКАЖИТЕ, ЧТО ОНО СООТВЕТСТВУЕТ ПОРАЗРЯДНОЙ СОРТИРОВКЕ, ИСПОЛЬЗУЮЩЕЙ 
СИСТЕМУ СЧИСЛЕНИЯ СО СМЕШАННЫМ ОСНОВАНИЕМ.

\ex[м28] в ТЕКСТЕ СХЕМАТИЧЕСКИ ПРЕДСТАВЛЕНА МНОГОФАЗНАЯ 
ПОРАЗРЯДНАЯ СОРТИРОВКА 21 КЛЮЧА! оБОБЩИТЕ ЕЕ НА СЛУЧАЙ $F_n$ КЛЮЧЕЙ; 
ОБЎЯСНИТЕ, КАКИЕ КЛЮЧИ И НА КАКОЙ ЛЕНТЕ ОКАЗЫВАЮТСЯ В КОНЦЕ КАЖДОЙ ФАЗЫ. 
[{\sl уКАЗАНИЕ:\/}
%% 417
РАССМОТРИТЕ СИСТЕМУ СЧИСЛЕНИЯ, ИСПОЛЬЗУЮЩУЮ ЧИСЛА фИБОНАЧЧИ; 
УПР. 1.2.8-34.]

\ex[м40] рАСПРОСТРАНИТЕ РЕЗУЛЬТАТЫ УПР.~2 НА МНОГОФАЗНУЮ ПОРАЗРЯДНУЮ 
СОРТИРОВКУ С ЧЕТЫРЬМЯ ИЛИ БОЛЬШИМ КОЛИЧЕСТВОМ ЛЕНТ (СР. С УПР.~5.4.2--10).

\ex[м20] дОКАЖИТЕ, ЧТО СХЕМА РАСПРЕДЕЛЕНИЯ эШЕНХЕРСТА СЛУЖИТ НАИЛУЧШИМ 
СПОСОБОМ СОРТИРОВКИ 10 КЛЮЧЕЙ НА ЧЕТЫРЕХ ЛЕНТАХ БЕЗ ОБРАТНОГО ЧТЕНИЯ В ТОМ 
СМЫСЛЕ, ЧТО СООТВЕТСТВУЮЩЕЕ ДЕРЕВО ИМЕЕТ МИНИМАЛЬНУЮ ДЛИНУ ВНЕШНЕГО ПУТИ 
СРЕДИ ВСЕХ "СИЛЬНЫХ 4-fifo ДЕРЕВЬЕВ". (тАКИМ ОБРАЗОМ, ЭТО, ПО СУЩЕСТВУ, 
НАИЛУЧШИЙ МЕТОД, ЕСЛИ НЕ УЧИТЫВАТЬ ВРЕМЯ ПЕРЕМОТКИ.)

\ex[15] нАРИСУЙТЕ 4-lifo ДЕРЕВО, СООТВЕТСТВУЮЩЕЕ ПОРАЗРЯДНОЙ 
СОРТИРОВКЕ мОЧЛИ С ОБРАТНЫМ ЧТЕНИЕМ 10 КЛЮЧЕЙ.

\rex[20] нЕКОТОРЫЙ ФАЙЛ СОДЕРЖИТ ДВУХРАЗРЯДНЫЕ КЛЮЧИ $00$, $01$, \dots, 
$99$. пОСЛЕ ВЫПОЛНЕНИЯ ПОРАЗРЯДНОЙ СОРТИОВКИ мОЧЛИ ПО ЦИФРЕ ЕДИНИЦ МЫ 
МОЖЕМ ПОВТОРИТЬ ТУ ЖЕ СХЕМУ ПО ЦИФРЕ ДЕСЯТКОВ, ПОМЕНЯВ РОЛЯМИ ЛЕНТЫ 
$T2$ И $T4$. в КАКОМ ПОРЯДКЕ В КОНЦЕ КОНЦОВ ОКАЖУТСЯ КЛЮЧИ НА $T2$?

\ex[21] пРИМЕНИМ ЛИ ПРИНЦИП ДВОЙСТВЕННОСТИ ТАКЖЕ И К ФАЙЛАМ НА 
НЕСКОЛЬКИХ БОБИНАХ?

\subsubchap{сОРТИРОВКА С ДВУМЯ ЛЕНТАМИ}
дЛЯ ТОГО ЧТОБЫ ПРИ ВЫПОЛНЕНИИ СЛИЯНИЯ НЕ БЫЛО ЧРЕЗМЕРНОГО ДВИЖЕНИЯ ЛЕНТ,
 НЕОБХОДИМЫ ТРИ ЛЕНТЫ. иНТЕРЕСНО ПОДУМАТЬ О ТОМ, КАК МОЖНО РАЗУМНЫМ 
ОБРАЗОМ ВЫПОЛНИТЬ ВНЕШНЮЮ СОРТИРОВКУ С ИСПОЛЬЗОВАНИЕМ ТОЛЬКО ДВУХ ЛЕНТ.

в 1956~Г. г.~б.~дЕМУТ ПРЕДЛОЖИЛ НЕКИЙ МЕТОД, ПРЕДСТАВЛЯЮЩИЙ СОБОЙ 
КОМБИНАЦИЮ ВЫБОРА С ЗАМЕЩЕНИЕМ И СОРТИРОВКИ МЕТОДОМ ПУЗЫРЬКА. 
пРЕДПОЛОЖИМ, ЧТО ИСХОДНЫЕ ДАННЫЕ ЗАНИМАЮТ ЛЕНТУ $T1$, И НАЧНЕМ С ТОГО, 
ЧТО ПРОЧИТАЕМ В ПАМЯТЬ $P+1$ ЗАПИСЕЙ. тЕПЕРЬ ВЫВЕДЕМ ЗАПИСЬ С 
НАИМЕНЬШИМ КЛЮЧОМ НА ЛЕНТУ $T2$ И ЗАМЕНИМ ЕЕ СЛЕДУЮЩЕЙ ИСХОДНОЙ ЗАПИСЬЮ. 
пРОДОЛЖАЕМ ВЫВОДИТЬ ЗАПИСИ, КЛЮЧ КОТОРЫХ В ТЕКУЩИЙ МОМЕНТ НАИМЕНЬШИЙ В 
ПАМЯТИ, СОХРАНЯЯ ДЕРЕВО ВЫБОРА ИЛИ ПРИОРИТЕТНУЮ ОЧЕРЕДЬ ИЗ $P+1$ ЭЛЕМЕНТОВ.
 кОГДА ВВОД НАКОНЕЦ ИСЧЕРПАЕТСЯ, В ПАМЯТИ ОКАЖУТСЯ НАИБОЛЬШИЕ $P$ 
КЛЮЧЕЙ ФАЙЛА; ВЫВЕДЕМ ИХ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. тЕПЕРЬ ПЕРЕМОТАЕМ ОБЕ 
ЛЕНТЫ И ПОВТОРИМ ЭТОТ ПРОЦЕСС, ЧИТАЯ С $T2$ И ЗАПИСЫВАЯ НА $T1$; КАЖДЫЙ 
ТАКОЙ ПРОХОД ПОМЕЩАЕТ ЕЩЕ ПО КРАЙНЕЙ МЕРЕ $P$ ЗАПИСЕЙ НА СВОИ МЕСТА. в 
ПРОГРАММУ МОЖНО ВСТРОИТЬ ПРОСТУЮ ПРОВЕРКУ ДЛЯ ОПРЕДЕЛЕНИЯ МОМЕНТА, КОГДА 
ВЕСЬ ФАЙЛ СТАНЕТ УПОРЯДОЧЕННЫМ. пОТРЕБУЕТСЯ НЕ БОЛЕЕ  
$\lceil(N-1)/P\rceil$  ПРОХОДОВ.

мИНУТНОЕ РАЗМЫШЛЕНИЕ ПОКАЗЫВАЕТ, ЧТО КАЖДЫЙ ПРОХОД ЭТОЙ ПРОЦЕДУРЫ 
ЭКВИВАЛЕНТЕН $P$ ПОСЛЕДОВАТЕЛЬНЫМ ПРОХОДАМ СОРТИРОВКИ МЕТОДОМ ПУЗЫРЬКА 
(АЛГОРИТМ 5.2.2в)! еСЛИ ЭЛЕМЕНТ ИМЕЕТ $P$ ИЛИ БОЛЕЕ ИНВЕРСИЙ, ТО ПРИ ВВОДЕ 
ОН ОКАЖЕТСЯ МЕНЬШЕ ВСЕХ ЭЛЕМЕНТОВ В ДЕРЕВЕ И ПОЭТОМУ БУДЕТ НЕМЕДЛЕННО 
ВЫВЕДЕН (ПОТЕРЯВ, ТАКИМ ОБРАЗОМ, $P$ ИНВЕРСИЙ). еСЛИ ЭЛЕМЕНТ ИМЕЕТ МЕНЕЕ 
$P$ ИНВЕРСИЙ, ТО ОН ПОПАДАЕТ В ДЕРЕВО ВЫБОРА И БУДЕТ ВЫВЕДЕН РАНЬШЕ ВСЕХ 
БОЛЬШИХ КЛЮЧЕЙ (ПОТЕРЯВ, ТАКИМ ОБРАЗОМ,
%% 418
ВСЕ СВОИ ИНВЕРСИИ). еСЛИ $P=1$, ТО ПРОИСХОДИТ ТО ЖЕ САМОЕ, ЧТО И В МЕТОДЕ 
ПУЗЫРЬКА, ПО ТЕОРЕМЕ 5.2.21.

оБЩЕЕ ЧИСЛО ПРОХОДОВ БУДЕТ, СЛЕДОВАТЕЛЬНО, РАВНО $\lceil I/P \rceil$, ГДЕ 
$I$---МАКСИМАЛЬНОЕ ЧИСЛО ИНВЕРСИЙ ЛЮБОГО ЭЛЕМЕНТА. пО ТЕОРИИ, РАЗВИТОЙ В 
П.~5.2.2, СРЕДНЕЕ ЗНАЧЕНИЕ $I$ ЕСТЬ 
$N-\sqrt{\pi N/2}+(2/3) +O(1/\sqrt{N})$.

еСЛИ ФАЙЛ НЕ СЛИШКОМ СИЛЬНО ПРЕВОСХОДИТ РАЗМЕР ОПЕРАТИВНОЙ ПАМЯТИ ИЛИ 
ЕСЛИ ОН ПЕРВОНАЧАЛЬНО ПОЧТИ УПОРЯДОЧЕН, ТО ЭТА СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА 
$P$-ГО ПОРЯДКА БУДЕТ ДОВОЛЬНО БЫСТРОЙ; В ДЕЙСТВИТЕЛЬНОСТИ ЕЕ МОЖНО 
ПРЕДПОЧЕСТЬ ДАЖЕ В ТОМ СЛУЧАЕ, КОГДА ИМЕЮТСЯ ДОПОЛНИТЕЛЬНЫЕ 
ЛЕНТОПРОТЯЖНЫЕ УСТРОЙСТВА, ТАК КАК ВЕСЬ ПРОЦЕСС СОРТИРОВКИ МОЖЕТ 
ЗАКОНЧИТЬСЯ РАНЬШЕ, ЧЕМ ОПЕРАТОР УСПЕЕТ УСТАНОВИТЬ ТРЕТЬЮ ЛЕНТУ! с 
ДРУГОЙ СТОРОНЫ, ОНА БУДЕТ РАБОТАТЬ ВЕСЬМА МЕДЛЕННО НАД ДОВОЛЬНО БОЛЬШИМИ 
ФАЙЛАМИ СО СЛУЧАЙНЫМ РАСПОЛОЖЕНИЕМ ЭЛЕМЕНТОВ, ТАК КАК ВРЕМЯ ЕЕ РАБОТЫ 
ПРИБЛИЗИТЕЛЬНО ПРОПОРЦИОНАЛЬНО $N^2$.

пОСМОТРИМ, КАК РЕАЛИЗУЕТСЯ ЭТОТ МЕТОД ДЛЯ 100000 ЗАПИСЕЙ В ПРИМЕРЕ ИЗ 
П.~5.4.6. нАМ НУЖНО РАЗУМНО ВЫБРАТЬ $P$, ЧТОБЫ УЧЕСТЬ МЕЖБЛОЧНЫЕ 
ПРОМЕЖУТКИ ПРИ СОВМЕЩЕНИИ ОПЕРАЦИЙ ЧТЕНИЯ И ЗАПИСИ С ВЫЧИСЛЕНИЯМИ. тАК 
КАК В ПРИМЕРЕ ПРЕДПОЛАГАЕТСЯ, ЧТО КАЖДАЯ ЗАПИСЬ ИМЕЕТ ДЛИНУ 100 ЛИТЕР, 
А 100000 ЛИТЕР ЗАПОЛНЯЮТ ПАМЯТЬ, ТО У НАС БУДЕТ МЕСТО ДЛЯ ДВУХ БУФЕРОВ 
ВВОДА И ДВУХ БУФЕРОВ ВЫВОДА РАЗМЕРА $B$, ЕСЛИ ВЫБРАТЬ ЗНАЧЕНИЯ $P$ И $B$, 
ТАКИЕ, ЧТО
$$
100 (P+1) +4B =100000.
\eqno(1)
$$
еСЛИ ИСПОЛЬЗОВАТЬ ОБОЗНАЧЕНИЯ П.~5.4.6, ТО ПРИБЛИЗИТЕЛЬНОЕ ВРЕМЯ РАБОТЫ 
КАЖДОГО ПРОХОДА ВЫРАЖАЕТСЯ КАК
$$
NC\omega\tau(1+\rho), \qquad \omega=(B+\gamma)/B.
\eqno (2)
$$
пОСКОЛЬКУ ЧИСЛО ПРОХОДОВ ОБРАТНО ПРОПОРЦИОНАЛЬНО $P$, МЫ ХОТИМ ВЫБРАТЬ 
ТАКОЕ $B$, КРАТНОЕ 100, КОТОРОЕ МИНИМИЗИРУЕТ ВЕЛИЧИНУ $\omega/P$. 
эЛЕМЕНТАРНЫЙ АНАЛИЗ ПОКАЗЫВАЕТ, ЧТО МИНИМУМ
ДОСТИГАЕТСЯ, КОГДА $B$ РАВНО ПРИБЛИЗИТЕЛЬНО 
$\sqrt{24975\gamma}+\gamma^2-\gamma$. пОЭТОМУ МЫ ВЫБИРАЕМ $B=3000$, $P=879$.
 пОЛОЖИВ В ПРИВЕДЕННЫХ ВЫШЕ ФОРМУЛАХ $N=100000$, ПОЛУЧАЕМ, ЧТО ЧИСЛО 
ПРОХОДОВ $\lceil I/P\rceil$ БУДЕТ .ОКОЛО 114, А. ОЦЕНКА ОБЩЕГО ВРЕМЕНИ 
РЕШЕНИЯ СОСТАВЛЯЕТ ПРИМЕРНО $8.57$~Ч (ПРЕДПОЛАГАЯ ДЛЯ УДОБСТВА, 
ЧТО ИСХОДНЫЕ ДАННЫЕ И ОКОНЧАТЕЛЬНЫЙ ВЫВОД ТАКЖЕ ИМЕЮТ $B=3000$). зДЕСЬ 
ПРЕДСТАВЛЕН СЛУЧАЙ, КОГДА ДАННЫЕ ЗАНИМАЮТ ОКОЛО $0.44$ БОБИНЫ; ПОЛНАЯ 
БОБИНА ПОТРЕБОВАЛА БЫ ПРИМЕРНО В ПЯТЬ РАЗ БОЛЬШЕ ВРЕМЕНИ. мОЖНО ПРОИЗВЕСТИ 
НЕКОТОРЫЕ УЛУЧШЕНИЯ, ПРЕДУСМОТРЕВ В АЛГОРИТМЕ ПЕРИОДИЧЕСКИЕ ПРЕРЫВАНИЯ И 
ПЕРЕСЫЛКУ ЗАПИСЕЙ С НАИБОЛЬШИМИ КЛЮЧАМИ НА ВСПОМОГАТЕЛЬНУЮ 
%% 419
ЛЕНТУ, КОТОРАЯ ЗАТЕМ СНИМАЕТСЯ, НЕСКОЛЬКУ ЭТИ ЗАПИСИ ПРОСТО 
КОПИРУЮТСЯ ТУДА И ОБРАТНО ПОСЛЕ ТОГО, КАК ОНИ УЖЕ ОКАЗАЛИСЬ НА СВОИХ МЕСТАХ.

\section пРИМЕНЕНИЕ БЫСТРОЙ СОРТИРОВКИ. еЩЕ ОДНИМ МЕТОДОМ ВНУТРЕННЕЙ 
СОРТИРОВКИ, КОТОРЫЙ ПРОХОДИТ ДАННЫЕ ПОЧТИ ПОСЛЕДОВАТЕЛЬНО, ЯВЛЯЕТСЯ 
ОБМЕННАЯ СОРТИРОВКА С РАЗДЕЛЕНИЕМ ИЛИ БЫСТРАЯ СОРТИРОВКА (АЛГОРИТМ 5.2.2Q) 
мОЖНО ЛИ ЕЕ ПРИСПОСОБИТЬ К ДВУМ ЛЕНТАМ? [N. в; Yoash, {\sl CACM\/}, {\bf 
8} (1965), 649.]

нЕТРУДНО УВИДЕТЬ КАК МОЖНО СДЕЛАТЬ ЭТО, ВОСПОЛЬЗОВАВШИСЬ ОБРАТНЫМ ЧТЕНИЕМ. 
пРЕДПОЛОЖИМ, ЧТО ДВЕ ЛЕНТЫ ПОМЕЧЕНЫ 0 И 1, И ПРЕДСТАВИМ, ЧТО ФАЙЛ 
РАСПОЛАГАЕТСЯ СЛЕДУЮЩИМ ОБРАЗОМ:
\picture{рАСПОЛОЖЕНИЕ ФАЙЛА НА ЛЕНТЕ, СТР. 419}
кАЖДАЯ ЛЕНТА ВЫСТУПАЕТ В КАЧЕСТВЕ СТЕКА. дВЕ ЛЕНТЫ ВМЕСТЕ, ИСПОЛЬЗУЕМЫЕ 
КАК ПРЕДСТАВЛЕНО ЗДЕСЬ, ДАЮТ ВОЗМОЖНОСТЬ СЧИТАТЬ ФАЙЛ ЛИНЕЙНЫМ СПИСКОМ, 
В КОТОРОМ МЫ МОЖЕМ ПЕРЕМЕЩАТЬ ТЕКУЩУЮ ПОЗИЦИЮ ВЛЕВО ИЛИ ВПРАВО, КОПИРУЯ 
ЭЛЕМЕНТЫ ИЗ ОДНОГО СТЕКА В ДРУГОЙ. сЛЕДУЮЩИЕ РЕКУРСИВНЫЕ ПОДПРОГРАММЫ 
ОПРЕДЕЛЯЮТ СООТВЕТСТВУЮЩУЮ ПРОЦЕДУРУ СОРТИРОВКИ.

\itemize
\li \strong{SORT00} [ОТСОРТИРОВАТЬ ВЕРХНИЙ ПОДФАЙЛ С ЛЕНТЫ $0$ И ВЕРНУТЬ 
ЕГО НА ЛЕНТУ $0$]. еСЛИ ПОДФАЙЛ ПОМЕЩАЕТСЯ В ОПЕРАТИВНУЮ ПАМЯТЬ, ТО 
ПРИМЕНИТЬ К НЕМУ ВНУТРЕННЮЮ СОРТИРОВКУ И ЗАТЕМ ВЕРНУТЬ ЕГО НА ЛЕНТУ. в 
ПРОТИВНОМ СЛУЧАЕ ВЫБРАТЬ ОДНУ ЗАПИСЬ $R$ ИЗ ПОДФАЙЛА; ПУСТЬ ЕЕ КЛЮЧОМ 
БУДЕТ $K$. чИТАЯ ЛЕНТУ $0$ В ОБРАТНОМ НАПРАВЛЕНИИ, КОПИРОВАТЬ ВСЕ ЗАПИСИ, 
КЛЮЧИ КОТОРЫХ $>K$, ПОЛУЧАЯ ТАКИМ ОБРАЗОМ НОВЫЙ "ВЕРХНИЙ" ПОДФАЙЛ НА ЛЕНТЕ 
$1$. тЕПЕРЬ, ЧИТАЯ ЛЕНТУ $0$ В ПРЯМОМ НАПРАВЛЕНИИ, КОПИРОВАТЬ ВСЕ ЗАПИСИ 
С КЛЮЧАМИ, РАВНЫМИ $K$, НА ЛЕНТУ $1$. зАТЕМ, ВНОВЬ ЧИТАЯ ЛЕНТУ $0$ В 
ОБРАТНОМ НАПРАВЛЕНИИ, КОПИРОВАТЬ ВСЕ ЗАПИСИ С КЛЮЧАМИ $<K$ НА ЛЕНТУ 1. 
вЫПОЛНИТЬ \strong{SORT10} НАД КЛЮЧАМИ $<K$, ЗАТЕМ СКОПИРОВАТЬ КЛЮЧИ, 
РАВНЫЕ $K$, НА ЛЕНТУ $0$ И, НАКОНЕЦ, ВЫПОЛНИВ \strong{SORT10} НАД КЛЮЧАМИ 
$>K$, ЗАВЕРШИТЬ СОРТИРОВКУ.

\li \strong{SORT01} [ОТСОРТИРОВАТЬ ВЕРХНИЙ ПОДФАЙЛ С ЛЕНТЫ 0 И ЗАПИСАТЬ 
ЕГО НА ЛЕНТУ 1]. аНАЛОГИЧНО \strong{SORт00}, НО ПОСЛЕДНЕЕ ОБРАЩЕНИЕ К 
\strong{"SORT10"} ЗАМЕНЕНО НА \strong{"SORT11"}, ЗА КОТОРЫМ 
СЛЕДУЕТ КОПИРОВАНИЕ КЛЮЧЕЙ  $\le K$ НА ЛЕНТУ 1.

\li \strong{SORT10} [ОТСОРТИРОВАТЬ ВЕРХНИЙ ПОДФАЙЛ С ЛЕНТЫ 1 И ЗАПИСАТЬ 
ЕГО НА ЛЕНТУ 0]. тАКАЯ ЖЕ, КАК \strong{SORT01}, НО МЕНЯЮТСЯ МЕСТАМИ 0 И~1, 
А ТАКЖЕ ОПЕРАТОРЫ ОТНОШЕНИЙ $<$ И~$>$.
%% 420
\li \strong{SORT11} [ОТСОРТИРОВАТЬ ВЕРХНИЙ ПОДФАЙЛ С ЛЕНТЫ 1 И ВЕРНУТЬ 
ЕГО НА ЛЕНТУ 1]. тАКАЯ ЖЕ, КАК \strong{SORT00}, НО МЕНЯЮТСЯ МЕСТАМИ 0 И 1, 
А ТАКЖЕ ОТНОШЕНИЯ $<$ И $>$. мОЖНО БЕЗ ТРУДА СПРАВИТЬСЯ С РЕКУРСИВНОЙ 
ПРИРОДОЙ ЭТИХ ПРОЦЕДУР, ЗАПИСЫВАЯ ПОДХОДЯЩУЮ УПРАВЛЯЮЩУЮ ИНФОРМАЦИЮ НА ЛЕНТЫ.
\itemend

еСЛИ СЧИТАТЬ, ЧТО ДАННЫЕ НАХОДЯТСЯ В СЛУЧАЙНОМ ПОРЯДКЕ И ВЕРОЯТНОСТЬ 
РАВНЫХ КЛЮЧЕЙ ПРЕНЕБРЕЖИМО МАЛА, ТО МОЖНО ОЦЕНИТЬ ВРЕМЯ РАБОТЫ ЭТОГО 
АЛГОРИТМА СЛЕДУЮЩИМ ОБРАЗОМ. пУСТЬ $M$---ЧИСЛО ЗАПИСЕЙ, ПОМЕЩАЮЩИХСЯ В 
ОПЕРАТИВНОЙ ПАМЯТИ. пУСТЬ $X_N$---СРЕДНЕЕ ЧИСЛО ЗАПИСЕЙ, ЧИТАЕМЫХ ВО ВРЕМЯ 
ПРИМЕНЕНИЯ \strong{SORT00} ИЛИ \strong{SORT11} К ПОДФАЙЛУ ИЗ $N$ ЗАПИСЕЙ,
 ГДЕ $N > M$, И ПУСТЬ $Y_N$---СООТВЕТСТВУЮЩАЯ ВЕЛИЧИНА ДЛЯ 
\strong{SORT01} И~\strong{SORT10}. тОГДА ИМЕЕМ:
$$
\eqalign{
 X_N&=\cases{
  0, & ЕСЛИ $N\le M$,\cr
  3N+1+{1\over N}\sum_{0\le k<N}(Y_k+Y_{N-1-k}), & ЕСЛИ $N>M$,\cr
 }\cr
 Y_N&=\cases{
  0, & ЕСЛИ $N\le M$,\cr
  3N+2+{1\over N}\sum_{0\le k<N}(Y_k+X_{N-1-k}+k), & ЕСЛИ $N>M$.\cr
 }\cr
}
\eqno(3)
$$
рЕШЕНИЕ ЭТИХ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ (СМ. УПР. 2) ПОКАЗЫВАЕТ, ЧТО ОБЩИЙ 
ОБЎЕМ ИНФОРМАЦИИ, ЧИТАЕМОЙ С ЛЕНТЫ В ТЕЧЕНИЕ ФАЗ ВНЕШНЕГО РАЗДЕЛЕНИЯ, В 
СРЕДНЕМ РАВЕН $6{2\over 3}N\ln N+O(N)$
ПРИ $N\to\infty$. мЫ ТАКЖЕ ЗНАЕМ ИЗ ФОРМУЛЫ (5.2.2--25), ЧТО СРЕДНЕЕ ЧИСЛО 
ФАЗ ВНУТРЕННЕЙ СОРТИРОВКИ БУДЕТ РАВНО $2(N+1)/(M+2)-1$.

еСЛИ МЫ ПРИМЕНИМ ЭТОТ АНАЛИЗ К ПРИМЕРУ 100000 ЗАПИСЕЙ, РАССМОТРЕННОМУ В 
П.~5.4.6, ПРИЧЕМ ВОСПОЛЬЗУЕМСЯ БУФЕРАМИ ПО 25000 ЛИТЕР И БУДЕМ СЧИТАТЬ, 
ЧТО ВРЕМЯ СОРТИРОВКИ ПОДФАЙЛА ИЗ $n\le M=1000$ ЗАПИСЕЙ РАВНО 
$2nC\omega\tau$, ТО ПОЛУЧИМ СРЕДНЕЕ ВРЕМЯ СОРТИРОВКИ, ПРИБЛИЗИТЕЛЬНО 
РАВНОЕ 103 МИН (ВКЛЮЧАЯ, КАК В СХЕМЕ а, ОКОНЧАТЕЛЬНУЮ ПЕРЕМОТКУ). иТАК, 
МЕТОД БЫСТРОЙ СОРТИРОВКИ В СРЕДНЕМ НЕПЛОХ; НО, КОНЕЧНО, В 
\emph{НАИХУДШЕМ} СЛУЧАЕ ОН УЖАСЕН И УСТУПАЕТ ДАЖЕ МЕТОДУ ПУЗЫРЬКА, 
ОБСУЖДАВШЕМУСЯ ВЫШЕ.
\section пОРАЗРЯДНАЯ СОРТИРОВКА. оБМЕННУЮ ПОРАЗРЯДНУЮ СОРТИРОВКУ
(АЛГОРИТМ 5.2.2R) МОЖНО АНАЛОГИЧНЫМ ОБРАЗОМ ПРИСПОСОБИТЬ ДЛЯ СОРТИРОВКИ С 
ДВУМЯ ЛЕНТАМИ, ТАК КАК ОН ОЧЕНЬ ПОХОЖ НА БЫСТРУЮ СОРТИРОВКУ. в КАЧЕСТВЕ 
ТРЮКА, КОТОРЫЙ ПОЗВОЛИЛ
ПРИМЕНИТЬ ОБА ЭТИ МЕТОДА, ИСПОЛЬЗОВАЛАСЬ ИДЕЯ ЧТЕНИЯ ФАЙЛА БОЛЕЕ ЧЕМ ОДИН 
РАЗ---ТО, ЧЕГО МЫ НИКОГДА НЕ ДЕЛАЛИ В ПРЕДЫДУЩИХ АЛГОРИТМАХ ДЛЯ ЛЕНТ.

%% 421

с ПОМОЩЬЮ ТОГО ЖЕ ТРЮКА МОЖНО ОСУЩЕСТВИТЬ ОБЫЧНУЮ ПОРАЗРЯДНУЮ 
СОРТИРОВКУ НА ДВУХ ЛЕНТАХ "СНАЧАЛА-ПО-МЛАДШЕЙ-ЦИФРЕ". иМЕЯ ИСХОДНЫЕ 
ДАННЫЕ НА $T1$, КОПИРУЕМ НА $T2$ ВСЕ ЗАПИСИ, КЛЮЧ КОТОРЫХ В ДВОИЧНОЙ 
СИСТЕМЕ ОКАНЧИВАЕТСЯ НА 0;
ЗАТЕМ ПОСЛЕ ПЕРЕМОТКИ $T1$ ЧИТАЕМ ЕЕ ВНОВЬ, КОПИРУЯ ЗАПИСИ С КЛЮЧАМИ, 
ОКАНЧИВАЮЩИМИСЯ НА 1. тЕПЕРЬ ПЕРЕМАТЫВАЮТСЯ ОБЕ ЛЕНТЫ И ВЫПОЛНЯЕТСЯ 
АНАЛОГИЧНАЯ ПАРА ПРОХОДОВ, НО С ЗАМЕНОЙ $T1$ НА $T2$ И ИСПОЛЬЗОВАНИЕМ 
\emph{ПРЕДПОСЛЕДНЕЙ} ДВОИЧНОЙ ЦИФРЫ. в ЭТОТ МОМЕНТ $T1$ БУДЕТ СОДЕРЖАТЬ 
ВСЕ ЗАПИСИ С КЛЮЧАМИ $(\ldots00)_2$, ЗА КОТОРЫМИ СЛЕДУЮТ ЗАПИСИ С КЛЮЧАМИ 
$(\ldots01)_2$, ЗАТЕМ $(\ldots10)_2$, ЗАТЕМ $(\ldots11)_2$. еСЛИ КЛЮЧИ 
ИМЕЮТ РАЗМЕР $b$ БИТОВ, НАМ ПОТРЕБУЕТСЯ, ЧТОБЫ ЗАВЕРШИТЬ СОРТИРОВКУ, 
ТОЛЬКО $2b$ ПРОХОДОВ ПО ВСЕМУ ФАЙЛУ.

пОДОБНУЮ ПОРАЗРЯДНУЮ СОРТИРОВКУ МОЖНО ПРИМЕНЯТЬ ТОЛЬКО К \emph{СТАРШИМ} 
$b$ БИТАМ КЛЮЧА ДЛЯ НЕКОТОРОГО РАЗУМНО ВЫБРАННОГО ЧИСЛА $b$; ТАКИМ 
ОБРАЗОМ, ЧИСЛО ИНВЕРСИЙ УМЕНЬШИТСЯ ПРИМЕРНО В $2^b$ РАЗ, ЕСЛИ КЛЮЧИ БЫЛИ 
РАВНОМЕРНО РАСПРЕДЕЛЕНЫ; И ТОГДА НЕСКОЛЬКО ПРОХОДОВ $P$-ПУТЕВОЙ СОРТИРОВКИ 
МЕТОДОМ ПУЗЫРЬКА ПОЗВОЛЯТ ЗАВЕРШИТЬ РАБОТУ.

нОВЫЙ, НО НЕСКОЛЬКО БОЛЕЕ СЛОЖНЫЙ ПОДХОД К РАСПРЕДЕЛЯЮЩЕЙ СОРТИРОВКЕ С 
ДВУМЯ ЛЕНТАМИ ПРЕДЛОЖИЛИ а. и. нИКИТИН И л. и. шОЛМОВ [{\sl 
кИБЕРНЕТИКА\/}, {\bf 2}, 6 (1966), 79--84]. иМЕЮТСЯ СЧЕТЧИКИ ЧИСЛА КЛЮЧЕЙ 
ПО ОДНОМУ НА КАЖДУЮ ВОЗМОЖНУЮ КОНФИГУРАЦИЮ СТАРШИХ БИТОВ, И НА ОСНОВЕ 
ЭТИХ СЧЕТЧИКОВ СТРОЯТСЯ ИСКУССТВЕННЫЕ КЛЮЧИ $\kappa_1$, $\kappa_2$, 
\dots, $\kappa_M$ ТАК, ЧТОБЫ ДЛЯ КАЖДОГО $i$ ЧИСЛО ДЕЙСТВИТЕЛЬНЫХ КЛЮЧЕЙ, 
ЛЕЖАЩИХ МЕЖДУ $\kappa_i$ И $\kappa_{i+1}$, БЫЛО МЕЖДУ ЗАРАНЕЕ 
ОПРЕДЕЛЕННЫМИ ГРАНИЦАМИ $P_1$ И $P_2$. тАКИМ ОБРАЗОМ, $M$ ЛЕЖИТ МЕЖДУ 
$\lceil  N/P_1 \rceil$ И $\lceil N/P_1\rceil$. еСЛИ СЧЕТЧИКИ СТАРШИХ БИТОВ 
НЕ ДАЮТ ДОСТАТОЧНОЙ ИНФОРМАЦИИ ДЛЯ ОПРЕДЕЛЕНИЯ ТАКИХ $\kappa_1$, 
$\kappa_2$, \dots, $\kappa_M$, ТО ДЕЛАЕТСЯ ЕЩЕ ОДИН ИЛИ НЕСКОЛЬКО 
ПРОХОДОВ ДЛЯ ПОДСЧЕТА ЧАСТОТЫ КОНФИГУРАЦИЙ МЕНЕЕ ЗНАЧАЩИХ БИТОВ ПРИ 
НЕКОТОРЫХ КОНФИГУРАЦИЯХ СТАРШИХ БИТОВ. пОСЛЕ ТОГО КАК ТАБЛИЦА 
ИСКУССТВЕННЫХ КЛЮЧЕЙ ПОСТРОЕНА, $2\lceil \log_2 M \rceil$  ПРОХОДОВ БУДЕТ 
ДОСТАТОЧНО ДЛЯ ЗАВЕРШЕНИЯ СОРТИРОВКИ. (эТОТ МЕТОД ТРЕБУЕТ ПРОСТРАНСТВА 
ПАМЯТИ, ПРОПОРЦИОНАЛЬНОГО $N$, И ПОЭТОМУ НЕ МОЖЕТ ИСПОЛЬЗОВАТЬСЯ ДЛЯ 
ВНЕШНЕЙ СОРТИРОВКИ ПРИ $N\to\infty$. нА ПРАКТИКЕ МЫ НЕ СТАНЕМ ИСПОЛЬЗОВАТЬ 
ЭТОТ МЕТОД ДЛЯ ФАЙЛОВ НА НЕСКОЛЬКИХ БОБИНАХ, И, СЛЕДОВАТЕЛЬНО, $M$ БУДЕТ 
СРАВНИТЕЛЬНО НЕВЕЛИКО, ТАК ЧТО ТАБЛИЦА ИСКУССТВЕННЫХ КЛЮЧЕЙ ЛЕГКО 
ПОМЕСТИТСЯ В ПАМЯТИ.)

\section иМИТАЦИЯ ДОПОЛНИТЕЛЬНЫХ ЛЕНТ. ф.~к.~хЕННИ И р.~э.~сТИРНЗ ИЗОБРЕЛИ 
ОБЩИЙ МЕТОД ИМИТАЦИИ $k$ ЛЕНТ ВСЕГО НА ДВУХ ЛЕНТАХ, ПРИЧЕМ ТАКИМ ОБРАЗОМ, 
ЧТО ТРЕБУЕМОЕ СУММАРНОЕ ПЕРЕМЕЩЕНИЕ ЛЕНТЫ ВОЗРАСТАЕТ ВСЕГО ЛИШЬ В $O(\log 
L)$ РАЗ, ГДЕ $L$---МАКСИМАЛЬНОЕ РАССТОЯНИЕ, КОТОРОЕ НУЖНО ПРОЙТИ НА ЛЮБОЙ ОДНОЙ
%% 422
ЛЕНТЕ [{\sl JACM\/}, {\bf 13} (1966), 533--546]. иХ ПОСТРОЕНИЕ В 
СЛУЧАЕ СОРТИРОВКИ МОЖНО СЛЕГКА УПРОСТИТЬ, ЧТО И СДЕЛАНО В СЛЕДУЮЩЕМ 
МЕТОДЕ, ПРЕДЛОЖЕННОМ р.~м.~кАРПОМ.

бУДЕМ ИМИТИРОВАТЬ ОБЫЧНОЕ СБАЛАНСИРОВАННОЕ СЛИЯНИЕ НА ЧЕТЫРЕХ ЛЕНТАХ, 
ИСПОЛЬЗУЯ ДВЕ ЛЕНТЫ: $T1$ И $T2$. нА ПЕРВОЙ ИЗ НИХ (Т. Е. НА $T1$) 
СОДЕРЖИМОЕ ИМИТИРУЕМЫХ ЛЕНТ ХРАНИТСЯ ТАКИМ СПОСОБОМ, КАК ИЗОБРАЖЕНО НА 
РИС.~86; ПРЕДСТАВИМ СЕБЕ, ЧТО ДАННЫЕ ЗАПИСАНЫ НА ЧЕТЫРЕХ ДОРОЖКАХ ПО ОДНОЙ 
ДЛЯ КАЖДОЙ ИМИТИРУЕМОЙ ЛЕНТЫ. (в ДЕЙСТВИТЕЛЬНОСТИ ЛЕНТА НЕ ИМЕЕТ ТАКИХ
\picture{рИС. 86. рАЗБИВКА ЛЕНТЫ $T1$ В КОНСТРУКЦИИ хЕННИ И сТИРНЗА}
ДОРОЖЕК; МЫ МЫСЛИМ БЛОКИ $1$, $5$, $9$, $13$, \dots  КАК ДОРОЖКУ $1$,
 БЛОКИ $2$, $6$, $10$, $14$, \dots КАК ДОРОЖКУ $2$ И Т. Д.) дРУГАЯ ЛЕНТА 
($T2$) ИСПОЛЬЗУЕТСЯ ТОЛЬКО ДЛЯ ВСПОМОГАТЕЛЬНОГО ХРАНЕНИЯ, ЧТОБЫ ПОМОЧЬ В 
ВЫПОЛНЕНИИ ПЕРЕСТАНОВОК НА $T1$.

бЛОКИ НА КАЖДОЙ ДОРОЖКЕ РАЗДЕЛЯЮТСЯ НА \emph{ЗОНЫ}, 
СОДЕРЖАЩИЕ СООТВЕТСТВЕННО $1$, $2$, $4$, $8$, \dots, $2^k$, \dots БЛОКОВ. 
зОНА $k$ НА КАЖДОЙ ДОРОЖКЕ ЛИБО ЗАПОЛНЕНА ТОЧНО $2^k$ БЛОКАМИ ДАННЫХ, ЛИБО 
ЦЕЛИКОМ ПУСТА. нАПРИМЕР, НА РИС.~86 НА ДОРОЖКЕ~$1$ ДАННЫЕ СОДЕРЖАТСЯ В 
ЗОНАХ~$1$ И~$3$; НА ДОРОЖКЕ $2$---В ЗОНАХ $0$, $1$ И~$2$; НА ДОРОЖКЕ $3$---В 
ЗОНАХ $0$ И~$2$; НА ДОРОЖКЕ 4---В ЗОНЕ~$1$, А ВСЕ ОСТАЛЬНЫЕ ЗОНЫ ПУСТЫ.

пРЕДПОЛОЖИМ, ЧТО МЫ СЛИВАЕМ ДАННЫЕ С ДОРОЖЕК $1$ И~$2$ НА ДОРОЖКУ~$3$. в 
ОПЕРАТИВНОЙ ПАМЯТИ эвм НАХОДЯТСЯ ДВА БУФЕРА, ИСПОЛЬЗУЕМЫЕ ДВУХПУТЕВЫМ 
СЛИЯНИЕМ ДЛЯ ВВОДА, А ТАКЖЕ ТРЕТИЙ БУФЕР---ДЛЯ ВЫВОДА. кОГДА БУФЕР ВВОДА ДЛЯ 
ДОРОЖКИ~$1$ СТАНЕТ ПУСТЫМ, МОЖНО ЗАПОЛНИТЬ ЕГО СЛЕДУЮЩИМ ОБРАЗОМ: НАЙТИ 
ПЕРВУЮ НЕПУСТУЮ ЗОНУ ДОРОЖКИ~$1$, СКАЖЕМ ЗОНУ $k$, И СКОПИРОВАТЬ ПЕРВЫЙ ЕЕ 
БЛОК В БУФЕР ВВОДА, ЗАТЕМ СКОПИРОВАТЬ ОСТАЛЬНЫЕ $2^k-1$ БЛОКОВ ДАННЫХ НА 
$T2$ И ПЕРЕМЕСТИТЬ ИХ В ЗОНЫ 0, 1, \dots, $k-1$ ДОРОЖКИ~1. (тЕПЕРЬ ЗОНЫ 0, 
1, \dots, $k-1$ ЗАПОЛНЕНЫ, ЗОНА $k$ ПУСТА.) аНАЛОГИЧНАЯ ПРОЦЕДУРА 
ИСПОЛЬЗУЕТСЯ ДЛЯ ЗАПОЛНЕНИЯ БУФЕРА ВВОДА ДЛЯ ДОРОЖКИ~2, КАК ТОЛЬКО ОН 
СТАНЕТ ПУСТЫМ. кОГДА БУФЕР ВЫВОДА ПОДГОТОВЛЕН ДЛЯ ЗАПИСИ НА ДОРОЖКУ~3, 
МЫ ОБРАЩАЕМ ЭТОТ ПРОЦЕСС, Т. Е. ПРОСМАТРИВАЕМ $T1$ ПОКА НЕ НАЙДЕТСЯ ПЕРВАЯ 
\emph{ПУСТАЯ} ЗОНА НА ДОРОЖКЕ~$3$, СКАЖЕМ ЗОНА~$k$, И В ТО ЖЕ ВРЕМЯ 
КОПИРУЕМ ДАННЫЕ ИЗ ЗОН 0, 1, \dots, $k-1$ НА $T2$. дАННЫЕ
%%423
НА $T2$, К КОТОРЫМ ПРИСОЕДИНЯЕТСЯ СОДЕРЖИМОЕ БУФЕРА ВЫВОДА, ИСПОЛЬЗУЮТСЯ 
ТЕПЕРЬ ДЛЯ ЗАПОЛНЕНИЯ ЗОНЫ $k$ НА ДОРОЖКЕ 3.

дЛЯ ЭТОЙ ПРОЦЕДУРЫ МЫ ДОЛЖНЫ УМЕТЬ ПИСАТЬ В СЕРЕДИНУ ЛЕНТЫ $T1$, НЕ 
РАЗРУШАЯ ПОСЛЕДУЮЩУЮ ИНФОРМАЦИЮ НА ЭТОЙ ЛЕНТЕ. кАК И В СЛУЧАЕ 
ОСЦИЛЛИРУЮЩЕЙ СОРТИРОВКИ С ПРЯМЫМ ЧТЕНИЕМ (П.~5.4.5), МОЖНО БЕЗ ОПАСЕНИЙ 
ВЫПОЛНЯТЬ ЭТО ДЕЙСТВИЕ, ЕСЛИ ПРИНЯТЬ МЕРЫ ПРЕДОСТОРОЖНОСТИ.

пОСКОЛЬКУ ПРОСМОТР ДО ЗОНЫ $k$ ВЫПОЛНЯЕТСЯ ТОЛЬКО ОДИН РАЗ ЗА КАЖДЫЕ $2^k$ 
ШАГОВ, ТО, ЧТОБЫ ПЕРЕПИСАТЬ $2^i-1$ БЛОКОВ С ДОРОЖКИ 1 В ПАМЯТЬ, 
ПОТРЕБУЕТСЯ ПЕРЕМЕСТИТЬ ЛЕНТУ НА $\sum_{v\le k<l} 2^{l-1-k}\cdot c \cdot 
2^k=cl2^{l-1}$, ГДЕ $c$---НЕКОТОРАЯ КОНСТАНТА. тАКИМ ОБРАЗОМ, КАЖДЫЙ ПРОХОД 
СЛИЯНИЯ ТРЕБУЕТ $O(N\log N)$ ШАГОВ. тАК КАК В СБАЛАНСИРОВАННОМ СЛИЯНИИ 
ИМЕЕТСЯ $O(\log N)$ ПРОХОДОВ, ТО ОБЩЕЕ ВРЕМЯ РАБОТУ БУДЕТ $O(N(\log 
N)^2)$, ЧТО АСИМПТОТИЧЕСКИ ЗНАЧИТЕЛЬНО ЛУЧШЕ, ЧЕМ НАИХУДШИЙ СЛУЧАЙ ДЛЯ БЫСТРОЙ 
СОРТИРОВКИ.

нО НА САМОМ ДЕЛЕ ЭТОТ МЕТОД ОКАЗЫВАЕТСЯ ПОЧТИ БЕСПОЛЕЗНЫМ, ЕСЛИ 
ПРИМЕНЯЕТСЯ ДЛЯ СОРТИРОВКИ 100000 ЗАПИСЕЙ ИЗ ПРИМЕРА П.~5.4.6, ПОСКОЛЬКУ 
ИНФОРМАЦИЯ, КОТОРАЯ ДОЛЖНА РАЗМЕЩАТЬСЯ НА ЛЕНТЕ $T1$, НЕ УМЕСТИТСЯ НА 
ОДНОЙ БОБИНЕ ЛЕНТЫ. и ДАЖЕ ЕСЛИ МЫ ПРЕНЕБРЕЖЕМ ЭТИМ ФАКТОМ И БУДЕМ 
ИСХОДИТЬ ИЗ САМЫХ ОПТИМИСТИЧЕСКИХ ПРЕДПОЛОЖЕНИЙ ОТНОСИТЕЛЬНО СОВМЕЩЕНИЯ 
ЧТЕНИЯ/ЗАПИСИ/ВЫЧИСЛЕНИЙ, ОТНОСИТЕЛЬНО ДЛИН МЕЖБЛОЧНЫХ ПРОМЕЖУТКОВ И Т. Д.,
 ТО НАЙДЕМ, ЧТО ДЛЯ ВЫПОЛНЕНИЯ СОРТИРОВКИ ПОТРЕБУЕТСЯ ОКОЛО 37~Ч! иТАК, 
ЭТОТ МЕТОД ПРЕДСТАВЛЯЕТ ЧИСТО АКАДЕМИЧЕСКИЙ ИНТЕРЕС: КОНСТАНТА В 
$O(N(\log N)^2)$ СЛИШКОМ ВЕЛИКА, ЧТОБЫ МЕТОД БЫЛ УДОВЛЕТВОРИТЕЛЕН ДЛЯ 
ПРАКТИЧЕСКИХ ЗНАЧЕНИЙ $N$.

\section оДНОЛЕНТОЧНАЯ СОРТИРОВКА. мОЖНО ЛИ ОБОЙТИСЬ ВСЕГО ОДНОЙ ЛЕНТОЙ? 
нЕТРУДНО ВИДЕТЬ, ЧТО СОРТИРОВКУ МЕТОДОМ ПУЗЫРЬКА $P$-ГО ПОРЯДКА МОЖНО 
ПРЕОБРАЗОВАТЬ В ОДНОЛЕНТОЧНУЮ СОРТИРОВКУ, НО РЕЗУЛЬТАТ БУДЕТ УЖАСЕН.

г.~б.~дЕМУТ [Ph.~D.~thesis (Stanford University, 1956), 85] СДЕЛАЛ 
НАБЛЮДЕНИЕ, ЧТО В ВЫЧИСЛИТЕЛЬНОЙ МАШИНЕ С ОГРАНИЧЕННОЙ ОПЕРАТИВНОЙ 
ПАМЯТЬЮ НЕЛЬЗЯ, УМЕНЬШИТЬ ЧИСЛО ИНВЕРСИЙ ПЕРЕСТАНОВКИ БОЛЬШЕ, ЧЕМ НА 
ОГРАНИЧЕННУЮ ВЕЛИЧИНУ, ПОСЛЕ ПРОСМОТРА ЛЕНТЫ НА ОГРАНИЧЕННОЕ РАССТОЯНИЕ; 
СЛЕДОВАТЕЛЬНО, ЛЮБОЙ АЛГОРИТМ СОРТИРОВКИ С ОДНОЙ ЛЕНТОЙ ПОТРЕБУЕТ В 
СРЕДНЕМ ПО КРАЙНЕЙ МЕРЕ $dN^2$ ЕДИНИЦ ВРЕМЕНИ (ГДЕ $d$---НЕКОТОРАЯ 
ПОЛОЖИТЕЛЬНАЯ КОНСТАНТА, ЗАВИСЯЩАЯ ОТ КОНФИГУРАЦИИ эвм).

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

%% 424

рАССМОТРИМ ЗДАНИЕ С $n$ ЭТАЖАМИ; ПОМЕЩЕНИЕ КАЖДОГО ЭТАЖА РАССЧИТАНО НА $c$ 
ЧЕЛОВЕК. в ЭТОМ ЗДАНИИ НЕТ НИ ОКОН, НИ ДВЕРЕЙ, НИ ЛЕСТНИЦ, НО ВСЕ ЖЕ ЕСТЬ 
ЛИФТ, КОТОРЫЙ МОЖЕТ ОСТАНАВЛИВАТЬСЯ НА ЛЮБОМ ЭТАЖЕ. в ЗДАНИИ НАХОДЯТСЯ 
$cn$ ЧЕЛОВЕК, И РОВНО $c$ ИЗ НИХ ХОТЯТ ПОПАСТЬ НА КАЖДЫЙ ОТДЕЛЬНЫЙ ЭТАЖ. в 
ЛИФТ ВМЕЩАЕТСЯ САМОЕ БОЛЬШЕЕ $b$ ЧЕЛОВЕК, И ОН ЗАТРАЧИВАЕТ ОДНУ ЕДИНИЦУ 
ВРЕМЕНИ ДЛЯ ПЕРЕМЕЩЕНИЯ С ЭТАЖА $i$ НА ЭТАЖ $i+1$. мЫ ХОТЕЛИ БЫ НАЙТИ 
БЫСТРЕЙШИЙ СПОСОБ ПЕРЕМЕСТИТЬ ВСЕХ ЛЮДЕЙ НА НУЖНЫЕ ЭТАЖИ, ЕСЛИ ТРЕБУЕТСЯ, 
ЧТОБЫ ЛИФТ НАЧАЛ И ЗАКОНЧИЛ СВОЕ ДВИЖЕНИЕ НА ПЕРВОМ ЭТАЖЕ.

нЕТРУДНО ЗАМЕТИТЬ СВЯЗЬ МЕЖДУ ЭТОЙ ЗАДАЧЕЙ И ОДНОЛЕНТОЧНОЙ СОРТИРОВКОЙ: 
ЛЮДИ---ЭТО ЗАПИСИ, ЗДАНИЕ---ЛЕНТА, ЭТАЖИ--- ОТДЕЛЬНЫЕ, БЛОКИ НА ЛЕНТЕ, А 
ЛИФТ---ОПЕРАТИВНАЯ ПАМЯТЬ эвм. дЕЙСТВИЯМ ПРОГРАММ ДЛЯ эвм СВОЙСТВЕННА 
БОЛЬШАЯ ГИБКОСТЬ, ЧЕМ ДЕЙСТВИЯМ ЛИФТЕРА (ОНА МОЖЕТ, НАПРИМЕР, СОЗДАВАТЬ 
ДВОЙНИКОВ ИЛИ, РАЗРЕЗАВ ЧЕЛОВЕКА НА ДВЕ ЧАСТИ, ОСТАВИТЬ ИХ НА ВРЕМЯ НА 
РАЗНЫХ ЭТАЖАХ И Т. Д.); НО В ПРИВОДИМОМ НИЖЕ АЛГОРИТМЕ ЗАДАЧА РЕШАЕТСЯ 
БЫСТРЕЙШИМ МЫСЛИМЫМ СПОСОБОМ БЕЗ ВЫПОЛНЕНИЯ ТАКИХ ОПЕРАЦИЙ. аЛГОРИТМ кАРПА 
ИСПОЛЬЗУЕТ СЛЕДУЮЩИЕ ДВА ВСПОМОГАТЕЛЬНЫХ МАССИВА:
$$
\eqalign{
u_k, 1\le k\le n:& 
\rem{ЧИСЛО ЛЮДЕЙ НА ЭТАЖАХ  $\le k$, СТРЕМЯЩИХСЯ ПОПАСТЬ НА ЭТАЖИ $>k$}\cr
d_k, 1\le k \le n:& 
\rem{ЧИСЛО ЛЮДЕЙ НА ЭТАЖАХ $\ge k$, СТРЕМЯЩИХСЯ ПОПАСТЬ НА ЭТАЖИ $<k$}\cr
}
\eqno(4)
$$.
кОГДА ЛИФТ ПУСТ, МЫ ВСЕГДА ИМЕЕМ $u_k=d_{k+1}$ ПРИ $1\le k < n$, ТАК КАК НА 
КАЖДОМ ЭТАЖЕ НАХОДЯТСЯ $c$ ЧЕЛОВЕК; КОЛИЧЕСТВО ЛЮДЕЙ, НАПРАВЛЯЮЩИХСЯ С 
ЭТАЖЕЙ $\{1, \ldots, k\}$ НА ЭТАЖИ $\{k+1, \ldots, П\}$, ДОЛЖНО РАВНЯТЬСЯ 
ЧИСЛУ ЛЮДЕЙ, СТРЕМЯЩИХСЯ ПЕРЕПРАВИТЬСЯ В ОБРАТНОМ НАПРАВЛЕНИИ. пО 
ОПРЕДЕЛЕНИЮ $u_n=d_1=0$.

яСНО, ЧТО ЛИФТ ДОЛЖЕН СДЕЛАТЬ ПО КРАЙНЕЙ МЕРЕ $\lceil u_k/b\rceil$ РЕЙСОВ 
С ЭТАЖА $k$ НА ЭТАЖ $k+1$ ПРИ $1\le k<n$, ТАК КАК ТОЛЬКО $b$ ПАССАЖИРОВ 
МОГУТ ПОДНЯТЬСЯ ЗА ОДИН РЕЙС. аНАЛОГИЧНО, ОН ДОЛЖЕН СДЕЛАТЬ НЕ МЕНЕЕ 
$\lceil d_k/b\rceil$ РЕЙСОВ С ЭТАЖА $k$ НА ЭТАЖ $k-1$. сЛЕДОВАТЕЛЬНО, 
ЛИФТУ ПОТРЕБУЕТСЯ ПО КРАЙНЕЙ МЕРЕ
$$
\sum_{1\le k\le n} (\lceil u_k/n\rceil+\lceil d_k/b\rceil)
\eqno (5)
$$
ЕДИНИЦ ВРЕМЕНИ ПРИ ЛЮБОМ ПРАВИЛЬНОМ ГРАФИКЕ РАБОТЫ. кАРП ОБНАРУЖИЛ, ЧТО 
ЭТА НИЖНЯЯ ГРАНИЦА ДЕЙСТВИТЕЛЬНО ДОСТИЖИМА, ЕСЛИ $u_1$, \dots,  $u_{n-1}$ НЕНУЛЕВЫЕ.

\proclaim тЕОРЕМА к. еСЛИ $u_k>0$ ПРИ $1\le k <n$, ТО СУЩЕСТВУЕТ 
ГРАФИК РАБОТЫ ЛИФТА, ПРИ КОТОРОМ ВСЕ ЛЮДИ ДОСТАВЛЯЮТСЯ НА СВОИ ЭТАЖИ ЗА 
МИНИМАЛЬНОЕ ВРЕМЯ (5).
%%425

\bye