\input style
\chapnotrue
\chapno=5\subchno=2\subsubchno=3
%% 188

пУСТЬ $s_l$---РАЗМЕР ПОДДЕРЕВА С КОРНЕМ~$l$, 
А~$M_N$---МУЛЬТИМНОЖЕСТВО~$\{s_1, s_2, \ldots, s_N\}$ ВСЕХ ЭТИХ РАЗМЕРОВ. 
иСПОЛЬЗУЯ (14) И (15), ЛЕГКО ВЫЧИСЛИТЬ~$M_N$ ПРИ ЛЮБОМ ЗАДАННОМ~$N$. в 
УПР.~5.1.4--20 ПОКАЗАНО, ЧТО ОБЩЕЕ ЧИСЛО СПОСОБОВ ПОСТРОИТЬ ПИРАМИДУ 
ИЗ ЦЕЛЫХ ЧИСЕЛ $\{1, 2, \ldots, N\}$ РАВНО
$$
N!/s_1s_2\ldots s_N= N!/\prod_{s\in M_N} s.
\eqno(16)
$$
нАПРИМЕР, ЧИСЛО СПОСОБОВ РАСПОЛОЖИТЬ 26 БУКВ $\{A, B, C, \ldots, Z\}$ НА 
РИС.~28 ТАК, ЧТОБЫ ПО ВЕРТИКАЛИ СОХРАНЯЛСЯ АЛФАВИТНЫЙ ПОРЯДОК, РАВНО
$$
26!/(26 \cdot 10 \cdot 6 \cdot 2 \cdot 1 \cdot 1^{12} \cdot 3^6 \cdot 7^2 
\cdot 15^1).
$$

тЕПЕРЬ МЫ В СОСТОЯНИИ ПРОАНАЛИЗИРОВАТЬ ФАЗУ ПОСТРОЕНИЯ ПИРАМИДЫ В 
АЛГОРИТМЕ~H, Т. Е. ВЫЧИСЛЕНИЯ, КОТОРЫЕ ЗАВЕРШАЮТСЯ ДО ТОГО, КАК В ШАГЕ H2 
ВПЕРВЫЕ ВЫПОЛНИТСЯ УСЛОВИЕ $l=1$. к СЧАСТЬЮ, БЛАГОДАРЯ СЛЕДУЮЩЕЙ НИЖЕ 
ТЕОРЕМЕ АНАЛИЗ ПОСТРОЕНИЯ ПИРАМИДЫ МОЖНО СВЕСТИ К ИЗУЧЕНИЮ НЕЗАВИСИМЫХ ОПЕРАЦИЙ ПРОТАСКИВАНИЯ.

\proclaim тЕОРЕМА H. еСЛИ ИСХОДНЫМИ ДАННЫМИ ДЛЯ АЛГОРИТМА H 
СЛУЖИТ СЛУЧАЙНАЯ ПЕРЕСТАНОВКА МНОЖЕСТВА $\{ 1, 2, \ldots, N\}$, ТО В 
ФАЗЕ ПОСТРОЕНИЯ ПИРАМИДЫ С ОДИНАКОВОЙ ВЕРОЯТНОСТЬЮ МОЖЕТ ПОЛУЧИТЬСЯ 
ЛЮБАЯ ИЗ $N! /\left(\prod_{s\in M_N} s\right)$ ВОЗМОЖНЫХ ПИРАМИД. бОЛЕЕ 
moГО,
ВСЕ $\floor{N/2}$ ОПЕРАЦИЙ ПРОТАСКИВАНИЯ, ВЫПОЛНЕННЫЕ ЗА ВРЕМЯ ЭТОЙ ФАЗЫ, 
"РАВНОМЕРНЫ" В ТОМ СМЫСЛЕ, ЧТО ПО ДОСТИЖЕНИИ ШАГА H8 ВСЕ $s_l$ ВОЗМОЖНЫХ 
ЗНАЧЕНИЙ ПЕРЕМЕННОЙ~$i$ РАВНОВЕРОЯТНЫ.

\proof пРИМЕНИМ МЕТОД, КОТОРЫЙ В ЧИСЛЕННОМ АНАЛИЗЕ НАЗЫВАЕТСЯ МЕТОДОМ 
"ОБРАТНОЙ ЗАДАЧИ". пУСТЬ В КАЧЕСТВЕ ОДНОГО ИЗ ВОЗМОЖНЫХ РЕЗУЛЬТАТОВ 
ОПЕРАЦИИ ПРОТАСКИВАНИЯ ЗАДАНА ПИРАМИДА $K_1$ \dots{} $K_N$ С КОРНЕМ В 
УЗЛЕ~$l$; ТОГДА ЯСНО, ЧТО ИМЕЕТСЯ ВСЕГО~$s_l$ ИСХОДНЫХ КОНФИГУРАЦИЙ $K'_1$ 
\dots{} $K'_N$ ФАЙЛА, КОТОРЫЕ ПОСЛЕ ПРОТАСКИВАНИЯ ДАЮТ ТАКОЙ РЕЗУЛЬТАТ. 
вСЕ ЭТИ ИСХОДНЫЕ КОНФИГУРАЦИИ ИМЕЮТ РАЗЛИЧНЫЕ ЗНАЧЕНИЯ $K'_l$, 
СЛЕДОВАТЕЛЬНО, РАССУЖДАЯ В ОБРАТНОМ НАПРАВЛЕНИИ, СУЩЕСТВУЕТ РОВНО $s_l$ 
$s_{l+1}$ \dots{} $s_N$ ИСХОДНЫХ ПЕРЕСТАНОВОК МНОЖЕСТВА 
$\{1, 2, \ldots, N\}$, КОТОРЫЕ ПОСЛЕ ЗАВЕРШЕНИЯ ОПЕРАЦИИ ПРОТАСКИВАНИЯ В 
ПОЗИЦИЮ~$l$ ДАЮТ КОНФИГУРАЦИЮ $K_1$ \dots{} $K_N$.

сЛУЧАЙ $l=1$ ТИПИЧЕН: ПУСТЬ $K_1$ \dots{} $K_N$---ПИРАМИДА, И ПУСТЬ $K'_1$ 
\dots{} $K'_N$---ФАЙЛ, КОТОРЫЙ ПРЕОБРАЗУЕТСЯ В $K_1$ \dots{} $K_N$ В 
РЕЗУЛЬТАТЕ ПРОТАСКИВАНИЯ ПРИ $l=1$, $K=K'_1$. еСЛИ $K=K_i$, ТО ДОЛЖНЫ
ИМЕТЬ МЕСТО РАВЕНСТВА $K'_i=K_{\floor{i/2}}$, 
$K'_{\floor{i/2}}=K_{\floor{i/4}}$ И Т. Д., ПРИ ЭТОМ $K'_j=K_j$ ДЛЯ ВСЕХ 
$j$, НЕ ЛЕЖАЩИХ НА ПУТИ ОТ~$1$ К~$i$. оБРАТНО, ПРИ ЛЮБОМ~$i$ В РЕЗУЛЬТАТЕ 
ТАКОГО ПОСТРОЕНИЯ ПОЛУЧАЕТСЯ ФАЙЛ $K'_1$ \dots{} $K'_N$, ТАКОЙ, ЧТО (a) 
ОПЕРАЦИЯ ПРОТАСКИВАНИЯ ПРЕОБРАЗУЕТ
%% 189
ФАЙЛ $K'_1$ \dots{} $K'_N$ В $K_1$ \dots{} $K_N$ И 
(b) $K_{\floor{j/2}}\ge K_j$ ПРИ $2 \le \floor{j/2}<j\le N$. 
сЛЕДОВАТЕЛЬНО, ВОЗМОЖНЫ РОВНО~$N$ 
ТАКИХ ФАЙЛОВ $K'_1$ \dots{} $K'_N$,  И ОПЕРАЦИЯ ПРОТАСКИВАНИЯ РАВНОМЕРНА. 
(пРИМЕР ДОКАЗАТЕЛЬСТВА ЭТОЙ ТЕОРЕМЫ СМ. В УПР.~22.)\proofend

оБРАЩАЯСЬ К ВЕЛИЧИНАМ $A$, $B$, $C$, $D$ В АНАЛИЗЕ ПРОГРАММЫ~H, МОЖНО 
ВИДЕТЬ, ЧТО РАВНОМЕРНАЯ ОПЕРАЦИЯ ПРОТАСКИВАНИЯ, ПРОИЗВОДИМАЯ НАД 
ПОДДЕРЕВОМ РАЗМЕРА~$s$, ДАЕТ ВКЛАД $\floor{s/2}/s$ В СРЕДНЕЕ ЗНАЧЕНИЕ 
ВЕЛИЧИНЫ~$A$; ЕЕ ВКЛАД В СРЕДНЕЕ ЗНАЧЕНИЕ ВЕЛИЧИНЫ~$B$ РАВЕН
$$
{1\over s}(0+1+1+2+\cdots+\floor{\log_2 s})=
{1\over s}\left(\sum_{1\le k\le s} \floor{\log_2 k}\right)=
{1\over s}((s+1)\floor{\log_2 s}-2^{\floor{\log_2 s}+1}+2)
$$
(СМ. УПР. 1.2.4--42); И ОНА ДАЕТ ВКЛАД~$2/s$ ИЛИ~$0$ В СРЕДНЕЕ ЗНАЧЕНИЕ 
ВЕЛИЧИНЫ~$D$ В ЗАВИСИМОСТИ ОТ ТОГО, ЯВЛЯЕТСЯ ЛИ~$s$ ЧЕТНЫМ ИЛИ НЕЧЕТНЫМ. 
нЕСКОЛЬКО СЛОЖНЕЕ ОПРЕДЕЛИТЬ СООТВЕТСТВУЮЩИЙ ВКЛАД В СРЕДНЕЕ ЗНАЧЕНИЕ 
ВЕЛИЧИНЫ~$C$, ТАК ЧТО ЭТА ЗАДАЧА ПРЕДОСТАВЛЯЕТСЯ ЧИТАТЕЛЮ (СМ. УПР.~26). 
пРОИЗВОДЯ СУММИРОВАНИЕ ПО ВСЕМ ОПЕРАЦИЯМ ПРОТАСКИВАНИЯ, НАХОДИМ, ЧТО 
СРЕДНЕЕ ЗНАЧЕНИЕ ВЕЛИЧИНЫ~$A$ ЗА ВРЕМЯ ПОСТРОЕНИЯ ПИРАМИДЫ РАВНО
$$
A'_N=\sum_{s\in M_N} \floor{s/2}/s;
\eqno(17)
$$
АНАЛОГИЧНЫЕ ФОРМУЛЫ ИМЕЮТ МЕСТО И ДЛЯ~$B$, $C$ И~$D$, ТАК ЧТО МОЖНО БЕЗ 
ОСОБОГО ТРУДА ТОЧНО ВЫЧИСЛИТЬ ЭТИ СРЕДНИЕ ЗНАЧЕНИЯ. в СЛЕДУЮЩЕЙ ТАБЛИЦЕ 
ПРИВЕДЕНЫ ТИПИЧНЫЕ РЕЗУЛЬТАТЫ:
\ctable{
\hfill\bskip$#$\bskip&&\hfill\bskip$#$\bskip\cr
N\hfill & A'_N\hfill & B'_N\hfill& C'_N\hfill & D'_N \hfill\cr
  99 &  19.18 &  68.35 &  42.95 & 0.00 \cr
  100&  19.93 &  69.39 &  42.71 & 1.84 \cr
  999&  196.16& 734.66 & 464.53 & 0.00 \cr
 1000&  196.94& 735.80 & 464.16 & 1.92 \cr
 9999& 1966.02& 7428.18&4695.54 & 0.00 \cr
10000& 1966.82& 7429.39&4695.06 & 1.97 \cr
10001& 1966.45& 7430.07&4695.84 & 0.00 \cr
10002& 1967.15& 7430.97& 4695.95& 1.73 \cr
}
чТО КАСАЕТСЯ АСИМПТОТИКИ, ТО В~$M_N$ МОЖНО НЕ ОБРАЩАТЬ ВНИМАНИЯ НА 
РАЗМЕРЫ ОСОБЫХ ПОДДЕРЕВЬЕВ, И ТОГДА МЫ НАЙДЕМ, НАПРИМЕР, ЧТО
$$
A'_N={N\over 2}\cdot{0\over1}+{N\over 4}\cdot{1\over3}+
{N\over8}\cdot{3\over7}+\cdots+O(\log N)=
\left(1-{1\over2}\alpha\right)N+O(\log N),
\eqno(18)
$$
%% 190
ГДЕ
$$
\alpha=\sum_{k\ge 1} {1\over 2^k-1}=
1.60669\ 51524\ 15291\ 76378\ 33015\ 23190\ 92458\ 04805\hbox{---}.
\eqno  (19)
$$
(эТО ЗНАЧЕНИЕ ПОЛУЧИЛ дЖ.~у.~рЕНЧ МЛАДШИЙ, ПОЛЬЗУЯСЬ ПРЕОБРАЗОВАНИЕМ 
РЯДА ИЗ УПР.~27.) пРИ БОЛЬШИХ~$N$ МОЖНО ИСПОЛЬЗОВАТЬ ПРИБЛИЖЕННЫЕ ФОРМУЛЫ
$$
\eqalign{
A'_N&\approx 0.1967N+0.3 \hbox{ ($N$ ЧЕТ.)}, 
  \quad 0.1967N-0.3 \hbox{($N$ НЕЧЕТ.)};\cr
B'_N&\approx 0.74403N-1.3\ln N;\cr
C'_N&\approx 0.47034N-0.8\ln N;\cr
D'_N&\approx 1.8 \pm 0.2 \hbox{ ($N$ ЧЕТ.)},
  \quad 0 \hbox{($N$ НЕЧЕТ.)}.\cr
}
\eqno(20)
$$
нЕТРУДНО ОПРЕДЕЛИТЬ ТАКЖЕ МАКСИМАЛЬНЫЕ И МИНИМАЛЬНЫЕ ЗНАЧЕНИЯ. дЛЯ 
ПОСТРОЕНИЯ ПИРАМИДЫ ТРЕБУЕТСЯ ВСЕГО $O(N)$ ШАГОВ (СР. С УПР.~23).

эТИМ, ПО СУЩЕСТВУ, ЗАВЕРШАЕТСЯ АНАЛИЗ ФАЗЫ ПОСТРОЕНИЯ ПИРАМИДЫ В 
АЛГОРИТМЕ~H. аНАЛИЗ ФАЗЫ ВЫБОРА---СОВСЕМ ДРУГАЯ ЗАДАЧА, КОТОРАЯ ЕЩЕ ОЖИДАЕТ 
СВОЕГО РЕШЕНИЯ! пУСТЬ ПИРАМИДАЛЬНАЯ СОРТИРОВКА ПРИМЕНЯЕТСЯ К 
$N$~ЭЛЕМЕНТАМ; ОБОЗНАЧИМ ЧЕРЕЗ $A''_N$, $B''_N$, $C''_N$ И~$D''_N$ СРЕДНИЕ 
ЗНАЧЕНИЯ ВЕЛИЧИН $A$, $B$, $C$ И~$D$ ВО ВРЕМЯ ФАЗЫ ВЫБОРА. пОВЕДЕНИЕ 
АЛГОРИТМА~H ПОДВЕРЖЕНО СРАВНИТЕЛЬНО МАЛЫМ КОЛЕБАНИЯМ ОКОЛО ЭМПИРИЧЕСКИ 
УСТАНОВЛЕННЫХ СРЕДНИХ ЗНАЧЕНИЙ
$$
\eqalign{
A''_N &\approx 0.152N;\cr
B''_N &\approx N\log_2N-2.61N;\cr
C''_N &\approx {1\over2}N\log_2N-1.4N;\cr
D''_N &\approx \ln N\pm 2;\cr
}
\eqno(21)
$$
ТЕМ НЕ МЕНЕЕ ДО СИХ ПОР НЕ НАЙДЕНО ПРАВИЛЬНОГО ТЕОРЕТИЧЕСКОГО ОБоЯСНЕНИЯ 
ЭТИМ КОНСТАНТАМ. рАССМОТРЕВ ОТДЕЛЬНЫЕ ОПЕРАЦИИ ПРОТАСКИВАНИЯ, НЕТРУДНО 
ВЫВЕСТИ ВЕРХНИЕ ОЦЕНКИ, УКАЗАННЫЕ В НЕРАВЕНСТВАХ (8), ХОТЯ, ЕСЛИ 
РАССМАТРИВАТЬ АЛГОРИТМ КАК ЦЕЛОЕ, ВЕРХНЮЮ ОЦЕНКУ ДЛЯ~$C$, ПО-ВИДИМОМУ, 
СЛЕДУЕТ УМЕНЬШИТЬ
ПРИБЛИЗИТЕЛЬНО ДО~${1\over 2}N\log_2 N$.

\excercises
\ex[10] яВЛЯЕТСЯ ЛИ СОРТИРОВКА ПОСРЕДСТВОМ ПРОСТОГО ВЫБОРА (АЛГОРИТМ S) 
"УСТОЙЧИВОЙ"?

\ex[15] пОЧЕМУ В АЛГОРИТМЕ S ОКАЗЫВАЕТСЯ БОЛЕЕ УДОБНЫМ НАХОДИТЬ СНАЧАЛА 
НАИБОЛЬШИЙ ЭЛЕМЕНТ, ЗАТЕМ НАИБОЛЬШИЙ ИЗ ОСТАВШИХСЯ И Т. Д , ВМЕСТО ТОГО 
ЧТОБЫ НАХОДИТЬ СНАЧАЛА НАИМЕНЬШИЙ ЭЛЕМЕНТ, ЗАТЕМ НАИМЕНЬШИЙ ИЗ 
ОСТАВШИХСЯ И Т. Д.?

%% 191
\ex[м21] (a) дОКАЖИТЕ, ЧТО ЕСЛИ АЛГОРИТМ S ПРИМЕНЯЕТСЯ К 
СЛУЧАЙНОЙ ПЕРЕСТАНОВКЕ МНОЖЕСТВА $\{1, 2, \ldots, N\}$, ТО В РЕЗУЛЬТАТЕ 
ПЕРВОГО ВЫПОЛНЕНИЯ ШАГОВ~S2 И~S3 ПОЛУЧАЕТСЯ СЛУЧАЙНАЯ ПЕРЕСТАНОВКА 
МНОЖЕСТВА $\{1, 2, \ldots, N-1\}$, ЗА КОТОРОЙ СЛЕДУЕТ~$N$. (иНАЧЕ ГОВОРЯ, 
ФАЙЛ $K_1$ \dots{} $K_{N-1}$ С ОДИНАКОВОЙ ВЕРОЯТНОСТЬЮ МОЖЕТ БЫТЬ ЛЮБОЙ 
ПЕРЕСТАНОВКОЙ МНОЖЕСТВА $\{1, 2, \ldots, N-1\}$.) (b) сЛЕДОВАТЕЛЬНО, ЕСЛИ 
ЧЕРЕЗ $B_N$ ОБОЗНАЧИТЬ СРЕДНЕЕ ЗНАЧЕНИЕ ВЕЛИЧИНЫ~$B$ В ПРОГРАММЕ~S, ТО ПРИ 
УСЛОВИИ, ЧТО ИСХОДНЫЙ ФАЙЛ УПОРЯДОЧЕН СЛУЧАЙНЫМ ОБРАЗОМ, 
ИМЕЕМ~$B_N=H_N-1+B_{N-1}$. [\emph{уКАЗАНИЕ:} СР. СО 
СТАТИСТИЧЕСКИМИ ХАРАКТЕРИСТИКАМИ 1.2.10--16.]

\rex[м35] в ШАГЕ~S3 АЛГОРИТМА~S НИЧЕГО НЕ ДЕЛАЕТСЯ, ЕСЛИ $i=j$. He 
ЛУЧШЕ ЛИ ПЕРЕД ВЫПОЛНЕНИЕМ ШАГА~S3 ПРОВЕРИТЬ УСЛОВИЕ~$i=j$? чЕМУ РАВНО 
СРЕДНЕЕ ЧИСЛО СЛУЧАЕВ ВЫПОЛНЕНИЯ УСЛОВИЯ $i=j$ В ШАГЕ~S3, ЕСЛИ ИСХОДНЫЙ ФАЙЛ 
СЛУЧАЕН?

\ex[20] чЕМУ РАВНО ЗНАЧЕНИЕ ВЕЛИЧИНЫ~$B$ В АНАЛИЗЕ ПРОГРАММЫ~S 
ДЛЯ ИСХОДНОГО ФАЙЛА $N \ldots 3\ 2\ 1$?

\ex[м29] (a) пУСТЬ $a_1$ $a_2$~\dots{} $a_N$---ПЕРЕСТАНОВКА МНОЖЕСТВА $\{1, 
2, \ldots, N\}$ С~$C$ ЦИКЛАМИ, $I$~ИНВЕРСИЯМИ И ТАКАЯ, ЧТО ПРИ ЕЕ 
СОРТИРОВКЕ С ПОМОЩЬЮ ПРОГРАММЫ~S ПРОИЗВОДИТСЯ $B$~ОБМЕНОВ НА 
ПРАВОСТОРОННИЙ МАКСИМУМ. дОКАЖИТЕ, ЧТО $2B\le I+N-C$. [\emph{уКАЗАНИЕ:} СМ.
 УПР.~5.2.2--1.] (b) пОКАЖИТЕ, ЧТО~$I+N-C\le\floor{n^2/2}$; СЛЕДОВАТЕЛЬНО, 
$B$ НЕ ПРЕВЫШАЕТ~$\floor{n^2/4}$.

\ex[м46] нАЙДИТЕ ДИСПЕРСИЮ ВЕЛИЧИНЫ~$B$ В ПРОГРАММЕ~S КАК ФУНКЦИЮ ОТ~$N$, 
СЧИТАЯ, ЧТО ИСХОДНЫЙ ФАЙЛ СЛУЧАЕН.

\ex[24] пОКАЖИТЕ, ЧТО ЕСЛИ ПРИ ПОИСКЕ~$\max(K_1, \ldots, K_j)$ В ШАГЕ S2 
ПРОСМАТРИВАТЬ КЛЮЧИ СЛЕВА НАПРАВО: $K_1$, $K_2$, \dots, $K_j$, А НЕ 
НАОБОРОТ: $K_j$, \dots, $K_2$, $K_1$, КАК В ПРОГРАММЕ~S, ТО ЗА СЧЕТ ЭТОГО 
МОЖНО БЫЛО БЫ СОКРАТИТЬ ЧИСЛО СРАВНЕНИЙ ПРИ СЛЕДУЮЩИХ ПОВТОРЕНИЯХ 
ШАГА~S2. нАПИШИТЕ \MIX-ПРОГРАММУ, ОСНОВАННУЮ НА ЭТОМ НАБЛЮДЕНИИ.

\ex[м25] чЕМУ РАВНО СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ, ВЫПОЛНЯЕМЫХ АЛГОРИТМОМ ИЗ 
УПР.~8 ДЛЯ СЛУЧАЙНОГО ИСХОДНОГО ФАЙЛА?

\ex[12] кАК БУДЕТ ВЫГЛЯДЕТЬ ДЕРЕВО, ИЗОБРАЖЕННОЕ НА РИС.~23, ПОСЛЕ ТОГО 
КАК БУДУТ ВЫВЕДЕНЫ~14 ИЗ~16 ПЕРВОНАЧАЛЬНЫХ ЭЛЕМЕНТОВ?

\ex[10] кАК БУДЕТ ВЫГЛЯДЕТЬ ДЕРЕВО, ИЗОБРАЖЕННОЕ НА РИС.~24, ПОСЛЕ ВЫВОДА 
ЭЛЕМЕНТА~$908$?

\ex[м20] сКОЛЬКО РАЗ БУДЕТ ВЫПОЛНЕНО СРАВНЕНИЕ~$-\infty$ С~$\infty$, 
ЕСЛИ ПРИМЕНИТЬ "ВОСХОДЯЩИЙ" МЕТОД, ПРЕДСТАВЛЕННЫЙ НА РИС.~23, ДЛЯ 
УПОРЯДОЧЕНИЯ ФАЙЛА ИЗ $2^n$~ЭЛЕМЕНТОВ?

\ex[20] (дЖ.~у.~дЖ.~уИЛЬЯМЕ.) в ШАГЕ~H4 АЛГОРИТМА~H РАЗЛИЧАЮТСЯ ТРИ 
СЛУЧАЯ: $j<r$, $j=r$ И~$j>r$. пОКАЖИТЕ, ЧТО ЕСЛИ $K\ge K_{r+1}$, ТО 
МОЖНО БЫЛО БЫ ТАК УПРОСТИТЬ ШАГ~H4, ЧТОБЫ РАЗВЕТВЛЕНИЕ ПРОИСХОДИЛО ЛИШЬ 
ПО ДВУМ ПУТЯМ. кАК НАДО ИЗМЕНИТЬ ШАГ~H2, ЧТОБЫ ОБЕСПЕЧИТЬ В ПРОЦЕССЕ 
ПИРАМИДАЛЬНОЙ СОРТИРОВКИ ВЫПОЛНЕНИЕ УСЛОВИЯ $K\ge K_{r+1}$?

\ex[10] пОКАЖИТЕ, ЧТО ПРОСТАЯ ОЧЕРЕДЬ---ЧАСТНЫЙ СЛУЧАЙ 
ПРИОРИТЕТНОЙ. (оБоЯСНИТЕ, КАКИЕ КЛЮЧИ НУЖНО ПРИСВАИВАТЬ ЭЛЕМЕНТАМ, ЧТОБЫ 
ПРОЦЕДУРА "НАИБОЛЬШИЙ ИЗ ВКЛЮЧЕННЫХ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ" БЫЛА ЭКВИВАЛЕНТНА 
ПРОЦЕДУРЕ "ПЕРВЫМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ".) яВЛЯЕТСЯ ЛИ СТЕК 
ТАКЖЕ ЧАСТНЫМ СЛУЧАЕМ ПРИОРИТЕТНОЙ ОЧЕРЕДИ?

\rex[M22] (в.~э.~чАРТРС.) пРИДУМАЙТЕ БЫСТРЫЙ АЛГОРИТМ ПОСТРОЕНИЯ ТАБЛИЦЫ 
ПРОСТЫХ ЧИСЕЛ $\le N$, В КОТОРОМ ИСПОЛЬЗУЕТСЯ \emph{ПРИОРИТЕТНАЯ 
ОЧЕРЕДЬ} С ЦЕЛЬЮ ИЗБЕЖАТЬ ОПЕРАЦИЙ ДЕЛЕНИЯ. [\emph{уКАЗАНИЕ.} пУСТЬ 
НАИМЕНЬШИЙ КЛЮЯ В ПРИОРИТЕТНОЙ ОЧЕРЕДИ БУДЕТ НАИМЕНЬШИМ НЕЧЕТНЫМ НЕПРОСТЫМ 
ЧИСЛОМ, БОЛЬШИМ, ЧЕМ САМОЕ ПОСЛЕДНЕЕ НЕЧЕТНОЕ ЧИСЛО, ВОСПРИНЯТОЕ КАК 
КАНДИДАТ В ПРОСТЫЕ ЧИСЛА. пОПЫТАЙТЕСЬ СВЕСТИ К МИНИМУМУ ЧИСЛО ЭЛЕМЕНТОВ 
В ЭТОЙ ОЧЕРЕДИ.]

\ex[20] пОСТРОЙТЕ ЭФФЕКТИВНЫЙ АЛГОРИТМ, КОТОРЫЙ ВСТАВЛЯЕТ НОВЫЙ КЛЮЧ В 
ДАННУЮ ПИРАМИДУ ИЗ П ЭЛЕМЕНТОВ, ПОРОЖДАЯ ПИРАМИДУ ИЗ $n+1$~ЭЛЕМЕНТОВ.

\ex[20] аЛГОРИТМ ИЗ УПР.~16 МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ ПОСТРОЕНИЯ ПИРАМИДЫ 
ВЗАМЕН МЕТОДА "УМЕНЬШЕНИЯ $l$ ДО~$1$", ПРИМЕНЯЕМОГО В АЛГОРИТМЕ~H.

%%192
пОРОЖДАЮТ ЛИ ОБА МЕТОДА ИЗ ОДНОГО И ТОГО ЖЕ ИСХОДНОГО ФАЙЛА ОДНУ И ТУ ЖЕ ПИРАМИДУ?

\rex[21] (р.~у.~фЛОЙД) вО ВРЕМЯ ФАЗЫ ВЫБОРА В АЛГОРИТМЕ ПИРАМИДАЛЬНОЙ 
СОРТИРОВКИ КЛЮЧ $K$, КАК ПРАВИЛО, ПРИНИМАЕТ ДОВОЛЬНО МАЛЫЕ ЗНАЧЕНИЯ, И 
ПОЭТОМУ ПОЧТИ ПРИ ВСЕХ СРАВНЕНИЯХ В ШАГЕ H6 ОБНАРУЖИВАЕТСЯ, ЧТО 
$K<K_j$. кАК. МОЖНО ИЗМЕНИТЬ АЛГОРИТМ, ЧТОБЫ КЛЮЧ $K$ НЕ СРАВНИВАЛСЯ 
С~$K_j$ В ОСНОВНОМ ЦИКЛЕ ВЫЧИСЛЕНИЙ?

\ex[21] пРЕДЛОЖИТЕ АЛГОРИТМ ИСКЛЮЧЕНИЯ ДАННОГО ЭЛЕМЕНТА ИЗ ПИРАМИДЫ 
РАЗМЕРА $N$, ПОРОЖДАЮЩИЙ ПИРАМИДУ РАЗМЕРА~$N-1$.

\ex[м20] пОКАЖИТЕ, ЧТО ФОРМУЛЫ (14) ЗАДАЮТ РАЗМЕРЫ ОСОБЫХ ПОДДЕРЕВЬЕВ ПИРАМИДЫ.

\ex[м24] дОКАЖИТЕ, ЧТО ФОРМУЛЫ (15) ЗАДАЮТ РАЗМЕРЫ НЕОСОБЫХ ПОДДЕРЕВЬЕВ ПИРАМИДЫ.

\rex[20] кАКИЕ ПЕРЕСТАНОВКИ МНОЖЕСТВА $\{1, 2, 3, 4, 5\}$ ФАЗА 
НОСТРОЕНИЯ ПИРАМИДЫ В АЛГОРИТМЕ~H ПРЕОБРАЗУЕТ В $5\ 3\ 4\ 1\ 2$?

\ex[м28] (a) дОКАЖИТЕ, ЧТО ДЛИНА ПУТИ~$B$ В АЛГОРИТМЕ 
ПРОТАСКИВАНИЯ НИКОГДА НЕ ПРЕВЫШАЕТ $\floor{\log_2(r/l)}$. (b) сОГЛАСНО 
НЕРАВЕНСТВАМ (8), НИ ПРИ КАКОМ КОНКРЕТНОМ ПРИМЕНЕНИИ АЛГОРИТМА~H 
ВЕЛИЧИНА~$B$ НЕ МОЖЕТ ПРЕВЗОЙТИ $N\floor{\log_2 N}$. нАЙДИТЕ МАКСИМАЛЬНОЕ 
ЗНАЧЕНИЕ~$B$ ПО ВСЕВОЗМОЖНЫМ ИСХОДНЫМ ФАЙЛАМ КАК ФУНКЦИЮ ОТ~$N$. (вЫ 
ДОЛЖНЫ ДОКАЗАТЬ, ЧТО СУЩЕСТВУЕТ ИСХОДНЫЙ ФАЙЛ, НА КОТОРОМ~$B$ ПРИНИМАЕТ 
ЭТО МАКСИМАЛЬНОЕ ЗНАЧЕНИЕ.)

\ex[м24] вЫВЕДИТЕ ТОЧНУЮ ФОРМУЛУ СТАНДАРТНОГО ОТКЛОНЕНИЯ 
ВЕЛИЧИНЫ~$B'_N$ (СУММАРНАЯ ДЛИНА ПУТИ, ПРОЙДЕННОГО ПО ДЕРЕВУ ВО ВРЕМЯ ФАЗЫ 
ПОСТРОЕНИЯ ПИРАМИДЫ В АЛГОРИТМЕ~H).

\ex[м20] чЕМУ РАВЕН СРЕДНИЙ ВКЛАД В ЗНАЧЕНИЕ ВЕЛИЧИНЫ~$C$ ЗА ВРЕМЯ ПЕРВОЙ 
ОПЕРАЦИИ ПРОТАСКИВАНИЯ, КОГДА $l=1$, a $r=N$, ЕСЛИ~$N=2^{n+1}-1$.

\ex[м30] рЕШИТЕ УПР.~25:  (a) ДЛЯ $N =26$, (b) ДЛЯ ПРОИЗВОЛЬНОГО~$N$.

\ex[м25] (дЖ.~у.~рЕНЧ~МЛ.) дОКАЖИТЕ, ЧТО 
$\sum_{n\ge 1} x^n/(1-x^n)=\sum_{n\ge 1} x^{n^2}(1+x^n)/(1-x^n)$. [пОЛОЖИВ 
$x={1\over2}$, ПОЛУЧИТЕ ОЧЕНЬ БЫСТРО СХОДЯЩИЙСЯ РЯД ДЛЯ ВЫЧИСЛЕНИЯ (19). )

\ex[35] пРОДУМАЙТЕ ИДЕЮ \emph{ТЕРНАРНЫХ ПИРАМИД}, ОСНОВАННЫХ НА 
ПОЛНЫХ ТЕРНАРНЫХ, А НЕ БИНАРНЫХ ДЕРЕВЬЯХ. бУДЕТ ЛИ ТЕРНАРНАЯ ПИРАМИДАЛЬНАЯ 
СОРТИРОВКА БЫСТРЕЕ БИНАРНОЙ?

\ex[26] (у. с. бРАУН.) пОСТРОЙТЕ АЛГОРИТМ УМНОЖЕНИЯ МНОГОЧЛЕНОВ 
ИЛИ СТЕПЕННЫХ 
РЯДОВ~$(a_1x^{i_1}+a_2x^{i_2}+\cdots)(b_1x^{j_1}+b_2x^{j_2}+\cdots)$, 
КОТОРЫЙ БЫ ПОРОЖДАЛ КОЭФФИЦИЕНТЫ ПРОИЗВЕДЕНИЯ $c_1x^{i_1+j_1}+\cdots$ ПО 
ПОРЯДКУ, ПО МЕРЕ ТОГО КАК ПЕРЕМНОЖАЮТСЯ КОЭФФИЦИЕНТЫ ИСХОДНЫХ 
МНОГОЧЛЕНОВ. [\emph{уКАЗАНИЕ:} 'ВОСПОЛЬЗУЙТЕСЬ ПОДХОДЯЩЕЙ ПРИОРИТЕТНОЙ ОЧЕРЕДЬЮ.]

\ex[м48] мОЖЕТ ЛИ ВЕЛИЧИНА~$C$ ПРЕВЗОЙТИ ${1\over2}N\log_2 N$ ПРИ 
ПИРАМИДАЛЬНОЙ СОРТИРОВКЕ ФАЙЛА? чЕМУ РАВНО МАКСИМАЛЬНОЕ ЗНАЧЕНИЕ~$C$? 
чЕМУ РАВНО МИНИМАЛЬНОЕ ЗНАЧЕНИЕ?

\ex[37] (дЖ.~у.~дЖ.~уИЛЬЯМЕ.) пОКАЖИТЕ, ЧТО ЕСЛИ ДВЕ ПИРАМИДЫ ПОДХОДЯЩИМ 
ОБРАЗОМ СОВМЕСТИТЬ "ОСНОВАНИЕ К ОСНОВАНИЮ", ТО ЭТО ДАСТ 
ВОЗМОЖНОСТЬ ПОДДЕРЖИВАТЬ СТРУКТУРУ, В КОТОРОЙ В ЛЮБОЙ МОМЕНТ МОЖНО ЗА 
$O(\log n)$~ШАГОВ ИСКЛЮЧИТЬ ЛИБО НАИБОЛЬШИЙ, ЛИБО НАИМЕНЬШИЙ ЭЛЕМЕНТ. 
(тАКУЮ СТРУКТУРУ МОЖНО НАЗВАТЬ \emph{ПРИОРИТЕТНЫМ ДЕКОМ}.)


\ex[21] рАЗРАБОТАЙТЕ АЛГОРИТМ СЛИЯНИЯ ДВУХ НЕПЕРЕСЕКАЮЩИХСЯ ПРИОРИТЕТНЫХ 
ОЧЕРЕДЕЙ, ПРЕДСТАВЛЕННЫХ В ВИДЕ ЛЕВОСТОРОННИХ ДЕРЕВЬЕВ, В ОДНУ. (в 
ЧАСТНОСТИ, ЕСЛИ ОДНА ИЗ ДАННЫХ ОЧЕРЕДЕЙ СОДЕРЖИТ ВСЕГО ОДИН ЭЛЕМЕНТ, ТО 
ВАШ АЛГОРИТМ БУДЕТ ВСТАВЛЯТЬ ЕГО В ДРУГУЮ ОЧЕРЕДЬ.) 

\rex[15] пОЧЕМУ В ПРИОРИТЕТНОЙ ОЧЕРЕДИ, ПРЕДСТАВЛЕННОЙ В ВИДЕ 
ЛЕВОСТОРОННЕГО ДЕРЕВА, ОПЕРАЦИЯ УДАЛЕНИЯ КОРНЯ ВЫПОЛНЯЕТСЯ ПУТЕМ СЛИЯНИЯ
%% 193
ДВУХ ПОДДЕРЕВЬЕВ, А НЕ "ПРОДВИЖЕНИЯ" УЗЛОВ ПО НАПРАВЛЕНИЮ К ВЕРШИНЕ, КАК В ПИРАМИДЕ?

\ex[м47] сКОЛЬКО МОЖНО ПОСТРОИТЬ ЛЕВОСТОРОННИХ ДЕРЕВЬЕВ ИЗ $N$~УЗЛОВ, ЕСЛИ 
ИГНОРИРОВАТЬ ЗНАЧЕНИЯ ПОЛЯ~|KEY|? [эТА ПОСЛЕДОВАТЕЛЬНОСТЬ НАЧИНАЕТСЯ С 
ЧИСЕЛ $1$, $1$, $2$, $4$, $8$, $17$, $38$, \dots; СУЩЕСТВУЕТ ЛИ 
КАКАЯ-НИБУДЬ ПРОСТАЯ АСИМПТОТИЧЕСКАЯ ФОРМУЛА?]

\ex[26] еСЛИ В ЛЕВОСТОРОННЕЕ ДЕРЕВО С~$N$ УЗЛАМИ ДОБАВИТЬ СВЯЗИ |UP| (СР. 
С ОБСУЖДЕНИЕМ ДЕРЕВЬЕВ С ТРЕМЯ СВЯЗЯМИ В П.~6.2.3), ТО ЭТО ДАСТ 
ВОЗМОЖНОСТЬ ИСКЛЮЧАТЬ ИЗ ПРИОРИТЕТНОЙ ОЧЕРЕДИ ПРОИЗВОЛЬНЫЙ УЗЕЛ~|P| 
СЛЕДУЮЩИМ ОБРАЗОМ: СЛИТЬ |LEFT(P)| И~|RIGHT(P)| И ПОМЕСТИТЬ ПОЛУЧЕННОЕ 
ПОДДЕРЕВО НА МЕСТО~|P|, ЗАТЕМ ИСПРАВЛЯТЬ ПОЛЯ~|DIST| У ПРЕДКОВ УЗЛА~|P| ДО 
ТЕХ ПОР, ПОКА НЕ БУДЕТ ДОСТИГНУТ ЛИБО КОРЕНЬ, ЛИБО УЗЕЛ, У КОТОРОГО 
ПОЛЕ~|DIST| НЕ МЕНЯЕТСЯ.

дОКАЖИТЕ, ЧТО ПРИ ЭТОМ НИКОГДА НЕ ПОТРЕБУЕТСЯ ИЗМЕНИТЬ БОЛЕЕ ЧЕМ $O(\log 
N)$ ПОЛЕЙ~|DIST|, НЕСМОТРЯ ДАЖЕ НА ТО, ЧТО ДЕРЕВО МОЖЕТ СОДЕРЖАТЬ. ОЧЕНЬ 
ДЛИННЫЕ ВОСХОДЯЩИЕ ПУТИ.

\ex[18] \emph{(зАМЕЩЕНИЕ НАИБОЛЕЕ ДАВНО ИСПОЛЬЗОВАННОЙ СТРАНИЦЫ.)} 
мНОГИЕ ОПЕРАЦИОННЫЕ СИСТЕМЫ ИСПОЛЬЗУЮТ АЛГОРИТМ СЛЕДУЮЩЕГО ТИПА: НАД 
НАБОРОМ УЗЛОВ ДОПУСТИМЫ ДВЕ ОПЕРАЦИИ---"ИСПОЛЬЗОВАНИЕ" УЗЛА И ЗАМЕЩЕНИЕ 
НАИБОЛЕЕ ДАВНО "ИСПОЛЬЗОВАННОГО" УЗЛА НОВЫМ УЗЛОМ. кАКАЯ СТРУКТУРА ДАННЫХ 
ОБЛЕГЧАЕТ НАХОЖДЕНИЕ НАИБОЛЕЕ ДАВНО "ИСПОЛЬЗОВАННОГО" УЗЛА?

\subsubchap{сОРТИРОВКА СЛИЯНИЕМ} %5.2.4
\dfn{сЛИЯНИЕ} ОЗНАЧАЕТ ОБоЕДИНЕНИЕ ДВУХ ИЛИ БОЛЕЕ УПОРЯДОЧЕННЫХ ФАЙЛОВ В 
ОДИН УПОРЯДОЧЕННЫЙ ФАЙЛ. мОЖНО, НАПРИМЕР, СЛИТЬ ДВА ПОДФАЙЛА---$503\ 703\ 
765$ И~$087\ 512\ 677$, 
ПОЛУЧИВ~$087\ 503\ 512\ 677\ 703\ 765$. пРОСТОЙ СПОСОБ СДЕЛАТЬ 
ЭТО---СРАВНИТЬ ДВА НАИМЕНЬШИХ ЭЛЕМЕНТА, ВЫВЕСТИ НАИМЕНЬШИЙ ИЗ НИХ И 
ПОВТОРИТЬ ЭТУ ПРОЦЕДУРУ.

нАЧАВ С
$$
\left\{\matrix{
 503 & 703 & 765 \cr
 087 & 512 & 677\cr
}\right.,
$$
ПОЛУЧИМ
$$
087\left\{\matrix{
503 & 703 & 765\cr
512 & 677 \cr
}\right.
$$
ЗАТЕМ
$$
087\ 503\ \left\{\matrix{
703 & 765\cr
512 & 677\cr
}\right.
$$
И~Т.~Д. нЕОБХОДИМО ПОЗАБОТИТЬСЯ О ДЕЙСТВИЯХ НА СЛУЧАЙ, КОГДА ИСЧЕРПАЕТСЯ 
ОДИН ИЗ ФАЙЛОВ. вЕСЬ ПРОЦЕСС ПОДРОБНО ОПИСАН В СЛЕДУЮЩЕМ АЛГОРИТМЕ.
\alg м.(дВУХПУТЕВОЕ СЛИЯНИЕ.) эТОТ АЛГОРИТМ ОСУЩЕСТВЛЯЕТ СЛИЯНИЕ ДВУХ 
УПОРЯДОЧЕННЫХ ФАЙЛОВ $x_1\le x_2\le\ldots\le x_m$ 
И~$y_1\le y_2 \le \ldots\le y_n$ В ОДИН ФАЙЛ 
$z_1\le z_2\le \ldots\le z_{m+n}$.
\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $i\asg 1$, $j\asg 1$, $k\asg 1$.
\st[нАЙТИ НАИМЕНЬШИЙ ЭЛЕМЕНТ.] еСЛИ $x_i\le y_j$, ТО ПЕРЕЙТИ К 
ШАГУ~\stp{3}; В ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ К~\stp{5}.
%%194
\st[вЫВЕСТИ $x_i$.] уСТАНОВИТЬ $z_k\asg x_i$,  $k\asg k+1$,  $i\asg i+1$. 
еСЛИ~$i\le m$, ТО ВОЗВРАТИТЬСЯ К \stp{2}.

\st[вЫВЕСТИ $y_j, \dots, y_n$.] уСТАНОВИТЬ 
$(z_k, \ldots, z_{m+n})\asg(y_j, \ldots, y_n)$ И ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА.

\st[вЫВЕСТИ $y_j$.] уСТАНОВИТЬ $z_k\asg y_j$, $k\asg k+1$, $j\asg j+1$.  
еСЛИ $j\le n$, ТО ВОЗВРАТИТЬСЯ К \stp{2}.
\st[вЫВЕСТИ $x_i$, \dots, $x_m$.] уСТАНОВИТЬ 
$(z_k, \ldots, z_{m+n})\asg(x_i, \ldots, x_m)$ И ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА.
\algend
\picture{рИС. 29. сЛИЯНИЕ $x_1\le \ldots\le x_m$ С $y_1\le\ldots\le y_n$.}

в П.~5.3.2 МЫ УВИДИМ, ЧТО ЭТА ПРОСТАЯ ПРОЦЕДУРА, ПО СУЩЕСТВУ, "НАИЛУЧШИЙ 
ИЗ ВОЗМОЖНЫХ" СПОСОБОВ СЛИЯНИЯ НА ТРАДИЦИОННОЙ эвм, ЕСЛИ $m\approx n$. 
(нО, ЕСЛИ $m$ ГОРАЗДО МЕНЬШЕ $n$, МОЖНО РАЗРАБОТАТЬ БОЛЕЕ ЭФФЕКТИВНЫЕ 
АЛГОРИТМЫ СОРТИРОВКИ, ХОТЯ В ОБЩЕМ СЛУЧАЕ ОНИ ДОВОЛЬНО СЛОЖНЫ.) аЛГОРИТМ~M 
БЕЗ ОСОБОЙ ПОТЕРИ ЭФФЕКТИВНОСТИ МОЖНО НЕМНОГО УПРОСТИТЬ, ДОБАВИВ В 
КОНЕЦ ИСХОДНЫХ ФАЙЛОВ ИСКУССТВЕННЫХ "СТРАЖЕЙ" $x_{m+1}=y_{n+1}=\infty$ 
И ОСТАНАВЛИВАЯСЬ ПЕРЕД ВЫВОДОМ~$\infty$. аНАЛИЗ АЛГОРИТМА~M СМ. В УПР.~2.

оБЩИЙ ОБоЕМ РАБОТЫ, ВЫПОЛНЯЕМОЙ АЛГОРИТМОМ~M, ПО СУЩЕСТВУ, 
ПРОПОРЦИОНАЛЕН $m+n$, ПОЭТОМУ ЯСНО, ЧТО СЛИЯНИЕ---БОЛЕЕ ПРОСТАЯ ЗАДАЧА, ЧЕМ 
СОРТИРОВКА. оДНАКО ЗАДАЧУ СОРТИРОВКИ МОЖНО СВЕСТИ К СЛИЯНИЯМ, СЛИВАЯ ВСЕ 
БОЛЕЕ ДЛИННЫЕ ПОДФАЙЛЫ ДО ТЕХ ПОР, ПОКА НЕ БУДЕТ ОТСОРТИРОВАН ВЕСЬ ФАЙЛ. 
тАКОЙ ПОДХОД МОЖНО РАССМАТРИВАТЬ КАК РАЗВИТИЕ ИДЕИ СОРТИРОВКИ ВСТАВКАМИ: 
ВСТАВКА НОВОГО ЭЛЕМЕНТА В УПОРЯДОЧЕННЫЙ ФАЙЛ---ЧАСТНЫЙ СЛУЧАЙ СЛИЯНИЯ ПРИ 
$n=1!$ еСЛИ НУЖНО УСКОРИТЬ ПРОЦЕСС ВСТАВОК, ТО МОЖНО РАССМОТРЕТЬ ВСТАВКУ 
НЕСКОЛЬКИХ ЭЛЕМЕНТОВ ЗА РАЗ, "ГРУППИРУЯ" ИХ, А ЭТО ЕСТЕСТВЕННЫМ ОБРАЗОМ 
ПРИВОДИТ К ОБЩЕЙ ИДЕЕ СОРТИРОВКИ СЛИЯНИЕМ. с ИСТОРИЧЕСКОЙ ТОЧКИ ЗРЕНИЯ 
МЕТОД СЛИЯНИЙ--- ОДИН ИЗ САМЫХ ПЕРВЫХ МЕТОДОВ, ПРЕДНАЗНАЧЕННЫХ ДЛЯ СОРТИРОВКИ
%% 195
\picture{тАБЛИЦА 1 сОРТИРОВКА ЕСТЕСТВЕННЫМ ДВУХПУТЕВЫМ СЛИЯНИЕМ}
НА эвм; ОН БЫЛ ПРЕДЛОЖЕН дЖОНОМ ФОН нЕЙМАНОМ ЕЩЕ В 1945~Г. (СМ. \S~5.5).

мЫ ДОВОЛЬНО ПОДРОБНО ИЗУЧИМ СЛИЯНИЯ В \S~5.4 В СВЯЗИ С АЛГОРИТМАМИ ВНЕШНЕЙ 
СОРТИРОВКИ, А В НАСТОЯЩЕМ ПУНКТЕ СОСРЕДОТОЧИМ СВОЕ ВНИМАНИЕ НА 
СОРТИРОВКЕ В БЫСТРОЙ ПАМЯТИ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ.

тАБЛИЦА~1 ИЛЛЮСТРИРУЕТ СОРТИРОВКУ СЛИЯНИЕМ, КОГДА "СВЕЧКА СЖИГАЕТСЯ С 
ОБОИХ КОНЦОВ", ПОДОБНО ТЕМ ПРОЦЕДУРАМ ПРОСМОТРА ЭЛЕМЕНТОВ ФАЙЛА, КОТОРЫЕ 
ПРИМЕНЯЛИСЬ ПРИ БЫСТРОЙ СОРТИРОВКЕ, ПОРАЗРЯДНОЙ ОБМЕННОЙ СОРТИРОВКЕ И~Т.~Д.
 мЫ АНАЛИЗИРУЕМ ИСХОДНЫЙ ФАЙЛ СЛЕВА И СПРАВА, ДВИГАЯСЬ К СЕРЕДИНЕ. 
пРОПУСТИМ ПОКА ПЕРВУЮ СТРОКУ И РАССМОТРИМ ПЕРЕХОД ОТ ВТОРОЙ СТРОКИ К 
ТРЕТЬЕЙ. сЛЕВА МЫ ВИДИМ ВОЗРАСТАЮЩИЙ ОТРЕЗОК $503$ $703$ $765$, А СПРАВА, 
ЕСЛИ ЧИТАТЬ СПРАВА НАЛЕВО, ИМЕЕМ ОТРЕЗОК $087$ $512$ $677$. сЛИЯНИЕ ЭТИХ 
ДВУХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДАЕТ ПОДФАЙЛ $087$ $503$ $512$ $677$ $703$ $765$, 
КОТОРЫЙ ПОМЕЩАЕТСЯ СЛЕВА В СТРОКЕ~3. зАТЕМ КЛЮЧИ $061$ $612$ $908$ В 
СТРОКЕ~2 СЛИВАЮТСЯ С~$170$ $509$ $897$, И РЕЗУЛЬТАТ $(061$ $170$ $509$ 
$612$ $897$ $908)$ ЗАПИСЫВАЕТСЯ \emph{СПРАВА} В СТРОКЕ~3. нАКОНЕЦ, $154$ 
$275$ $426$ $653$ СЛИВАЕТСЯ С $653$ (ПЕРЕКРЫТИЕ ОБНАРУЖИВАЕТСЯ ПРЕЖДЕ, 
ЧЕМ ОНО МОЖЕТ ПРИВЕСТИ К ВРЕДНЫМ ПОСЛЕДСТВИЯМ), И РЕЗУЛЬТАТ ЗАПИСЫВАЕТСЯ 
СЛЕВА. тОЧНО ТАК ЖЕ СТРОКА~2 ПОЛУЧИЛАСЬ ИЗ ИСХОДНОГО ФАЙЛА В СТРОКЕ~1.
 
вЕРТИКАЛЬНЫМИ ЛИНИЯМИ В ТАБЛ.~1 ОТМЕЧЕНЫ ГРАНИЦЫ МЕЖДУ ОТРЕЗКАМИ. эТО ТАК 
НАЗЫВАЕМЫЕ "СТУПЕНЬКИ ВНИЗ", ГДЕ МЕНЬШИЙ ЭЛЕМЕНТ СЛЕДУЕТ ЗА БОЛЬШИМ. в 
СЕРЕДИНЕ ФАЙЛА ОБЫЧНО ВОЗНИКАЕТ ДВУСМЫСЛЕННАЯ СИТУАЦИЯ, КОГДА ПРИ ДВИЖЕНИИ 
С ОБОИХ КОНЦОВ МЫ ПРОЧИТЫВАЕМ ОДИН И ТОТ ЖЕ КЛЮЧ; ЭТО НЕ ПРИВЕДЕТ К 
ОСЛОЖНЕНИЯМ, ЕСЛИ ПРОЯВИТЬ ЧУТОЧКУ ОСТОРОЖНОСТИ, КАК В 
СЛЕДУЮЩЕМ АЛГОРИТМЕ. тАКОЙ МЕТОД ПО ТРАДИЦИИ НАЗЫВАЕТСЯ 
"ЕСТЕСТВЕННЫМ" СЛИЯНИЕМ, ПОТОМУ ЧТО ОН ИСПОЛЬЗУЕТ ОТРЕЗКИ, КОТОРЫЕ 
"ЕСТЕСТВЕННО" ОБРАЗУЮТСЯ В ИСХОДНОМ ФАЙЛЕ.

\alg N.(сОРТИРОВКА ЕСТЕСТВЕННЫМ ДВУХПУТЕВЫМ СЛИЯНИЕМ.) пРИ СОРТИРОВКЕ 
ЗАПИСЕЙ $R_1$, \dots, $R_N$ ИСПОЛЬЗУЮТСЯ ДВЕ ОБЛАСТИ ПАМЯТИ, КАЖДАЯ ИЗ 
КОТОРЫХ МОЖЕТ СОДЕРЖАТЬ $N$~ЗАПИСЕЙ. дЛЯ УДОБСТВА ОБОЗНАЧИМ ЗАПИСИ, 
НАХОДЯЩИЕСЯ ВО ВТОРОЙ ОБЛАСТИ,
%%196
ЧЕРЕЗ $R_{N+1}$, \dots, $R_{2N}$, ХОТЯ В ДЕЙСТВИТЕЛЬНОСТИ ЗАПИСЬ~$R_{N+1}$ 
МОЖЕТ И НЕ ПРИМЫКАТЬ НЕПОСРЕДСТВЕННО К~$R_N$. нАЧАЛЬНОЕ СОДЕРЖИМОЕ ЗАПИСЕЙ 
$R_{N+1}$, \dots, $R_{2N}$ НЕ ИМЕЕТ ЗНАЧЕНИЯ. пОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ 
КЛЮЧИ БУДУТ УПОРЯДОЧЕНЫ: $K_1\le\ldots\le K_N$.
\picture{рИС. 30.  сОРТИРОВКА СЛИЯНИЕМ.}

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $s\asg0$. (пРИ $s=0$ МЫ БУДЕМ 
ПЕРЕСЫЛАТЬ ЗАПИСИ ИЗ ОБЛАСТИ $(R_1, \ldots, R_N)$ В ОБЛАСТЬ $(R_{N+1}, 
\ldots, R_{2N})$; ПРИ $s=1$ ОБЛАСТИ ПО ОТНОШЕНИЮ К ПЕРЕСЫЛКАМ ПОМЕНЯЮТСЯ РОЛЯМИ.)

\st[пОДГОТОВКА К ПРОСМОТРУ.] еСЛИ $s=0$, ТО УСТАНОВИТЬ $i\asg1$, 
$j\asg N$, $k\asg N+1$, $l\asg2N$; ЕСЛИ $s=1$, ТО УСТАНОВИТЬ $i\asg N+1$, 
$j\asg2N$, $k\asg1$, $l\asg N$. (пЕРЕМЕННЫЕ $i$, $j$, $k$, $l$ УКАЗЫВАЮТ 
ТЕКУЩИЕ ПОЗИЦИИ ВО ВХОДНЫХ "ФАЙЛАХ", ОТКУДА ИДЕТ ЧТЕНИЕ, И В ВЫХОДНЫХ 
"ФАЙЛАХ", КУДА ИДЕТ ЗАПИСЬ.) уСТАНОВИТЬ $d\asg 1$, $f\asg1$. 
(пЕРЕМЕННАЯ~$d$ ОПРЕДЕЛЯЕТ ТЕКУЩЕЕ НАПРАВЛЕНИЕ ВЫВОДА, $f$ 
УСТАНАВЛИВАЕТСЯ РАВНОЙ~0, ЕСЛИ НЕОБХОДИМЫ ДАЛЬНЕЙШИЕ ПРОСМОТРЫ.)

\st[сРАВНЕНИЕ $K_i:K_j$] еСЛИ $K_i>K_j$, ПЕРЕЙТИ К ШАГУ~\stp{8}. еСЛИ 
$i=j$, УСТАНОВИТЬ $P_k\asg R_i$ И ПЕРЕЙТИ К ШАГУ \stp{13}.

\st[пЕРЕСЫЛКА $R_i$.] (шАГИ \stp{4}--\stp{7} АНАЛОГИЧНЫ ШАГАМ 
M3--M4 АЛГОРИТМА~M.) уСТАНОВИТЬ $R_k\asg R_i$, $k\asg k+d$.

\st[сТУПЕНЬКА ВНИЗ?] уВЕЛИЧИТЬ $i$ НА~1. зАТЕМ, ЕСЛИ $K_{i-1}\le K_i$, 
ВОЗВРАТИТЬСЯ К ШАГУ \stp{3}.
\st [пЕРЕСЫЛКА $R_j$.] уСТАНОВИТЬ $R_k\asg R_j$, 
$k\asg k+d$.
\st[сТУПЕНЬКА ВНИЗ?] уМЕНЬШИТЬ $j$ НА~1. зАТЕМ, ЕСЛИ $K_{j+1}\le K_j$, 
ВОЗВРАТИТЬСЯ К ШАГУ \stp{6}; В ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ К ШАГУ \stp{12}.

%% 197
\st[пЕРЕСЫЛКА $R_j$.] (шАГИ \stp{8}--\stp{11} ДВОЙСТВЕННЫ ПО ОТНОШЕНИЮ К 
ШАГАМ~\stp{4}--\stp{7}.) уСТАНОВИТЬ $R_k\asg R_j$, $k\asg k+d$.

\st[сТУПЕНЬКА ВНИЗ?] уМЕНЬШИТЬ $j$ НА 1. зАТЕМ, ЕСЛИ 
$K_{j+1}\le K_j$, ВОЗВРАТИТЬСЯ К ШАГУ \stp{3}.

\st[пЕРЕСЫЛКА $R_i$.] уСТАНОВИТЬ~$R_k\asg R_i$, $k\asg k+d$.

\st[сТУПЕНЬКА ВНИЗ?] уВЕЛИЧИТЬ $i$ НА~$1$. зАТЕМ, ЕСЛИ 
$K_{i-1}\le K_i$, ВОЗВРАТИТЬСЯ К ШАГУ \stp{10}.

\st[пЕРЕКЛЮЧЕНИЕ НАПРАВЛЕНИЯ.] уСТАНОВИТЬ $f\asg0$, $d\asg-d$ И 
ВЗАИМОЗАМЕНИТЬ $k\xchg l$. вОЗВРАТИТЬСЯ К ШАГУ \stp{3}.

\st[пЕРЕКЛЮЧЕНИЕ ОБЛАСТЕЙ.] еСЛИ $f=0$, ТО УСТАНОВИТЬ $s\asg 1-s$ И 
ВОЗВРАТИТЬСЯ К~\stp{2}. в ПРОТИВНОМ СЛУЧАЕ СОРТИРОВКА ЗАВЕРШЕНА; ЕСЛИ 
$s=0$, ТО УСТАНОВИТЬ 
$(R_1,~\ldots, R_N)\asg(R_{N+1}, \ldots, R_{2N})$. (еСЛИ РЕЗУЛЬТАТ МОЖНО 
ОСТАВИТЬ В ОБЛАСТИ~$(R_{N+1}, \ldots, R_{2N})$,  ТО ПОСЛЕДНЕЕ КОПИРОВАНИЕ НЕОБЯЗАТЕЛЬНО.)
\algend

в ЭТОМ АЛГОРИТМЕ ЕСТЬ ОДНА НЕБОЛЬШАЯ ТОНКОСТЬ, КОТОРАЯ ОБоЯСНЯЕТСЯ В УПР.~5.

зАПРОГРАММИРОВАТЬ АЛГОРИТМ~N ДЛЯ МАШИНЫ~\MIX\ НЕТРУДНО, НО ОСНОВНЫЕ 
СВЕДЕНИЯ О ЕГО ПОВЕДЕНИИ МОЖНО ПОЛУЧИТЬ И БЕЗ ПОСТРОЕНИЯ ВСЕЙ ПРОГРАММЫ. 
еСЛИ ФАЙЛ СЛУЧАЕВ, ТО В НЕМ ОКОЛО
${1\over2}N$ ВОЗРАСТАЮЩИХ ОТРЕЗКОВ, ТАК КАК $K_i>K_{i+1}$ С 
ВЕРОЯТНОСТЬЮ~$1\over2$; ПОДРОБНАЯ ИНФОРМАЦИЯ О ЧИСЛЕ ОТРЕЗКОВ ПРИ 
НЕСКОЛЬКО ОТЛИЧНЫХ ПРЕДПОЛОЖЕНИЯХ БЫЛА ПОЛУЧЕНА В П.~5.1.3. пРИ КАЖДОМ 
ПРОСМОТРЕ ЧИСЛО ОТРЕЗКОВ СОКРАЩАЕТСЯ ВДВОЕ (ЗА ИСКЛЮЧЕНИЕМ НЕОБЫЧНЫХ 
СЛУЧАЕВ, ТАКИХ, КАК СИТУАЦИЯ, ОПИСАННАЯ В УПР.~6). тАКИМ ОБРАЗОМ, ЧИСЛО 
ПРОСМОТРОВ, КАК ПРАВИЛО, СОСТАВЛЯЕТ ОКОЛО~$\log_2 N$. пРИ КАЖДОМ ПРОСМОТРЕ 
МЫ ДОЛЖНЫ ПЕРЕПИСАТЬ ВСЕ $N$~ЗАПИСЕЙ, И, КАК ПОКАЗАНО В УПР.~2, Б\'ОЛЬШАЯ 
ЧАСТЬ ВРЕМЕНИ ЗАТРАЧИВАЕТСЯ В ШАГАХ~N3, N4, N5, N8, 
N9. еСЛИ СЧИТАТЬ, ЧТО РАВНЫЕ КЛЮЧИ ВСТРЕЧАЮТСЯ С МАЛОЙ ВЕРОЯТНОСТЬЮ, 
ТО ВРЕМЯ, ЗАТРАЧИВАЕМОЕ ВО ВНУТРЕННЕМ ЦИКЛЕ, МОЖНО 
ОХАРАКТЕРИЗОВАТЬ СЛЕДУЮЩИМ ОБРАЗОМ:
\ctable{
\hfill# & # & #\cr
\hbox{шАГ}\hfill&\hfill\hbox{оПЕРАЦИИ}\hfill&\hfill\hbox{вРЕМЯ}\hfill\cr
$\matrix{N3\cr}$ & $\matrix{|CMPA|, |JG|, |JE|\cr}$ & $\matrix{3.5u}$ \cr
$\hbox{лИБО}\left\{
\matrix{
N4\cr
N5\cr
}\right.$
& 
$
\matrix{
|STA|, |INC| \hfill\cr
|INC|, |LDA|, |CMPA|, |JGE|\hfill \cr
}
$
&
$\matrix{
\phantom{0.}3u\cr
\phantom{0.}6u\cr
}$
\cr 
$\hbox{лИБО}\left\{
\matrix{
N8 \cr
N9 \cr
}\right.$
&
$\matrix{
|STX|, |INC|\hfill \cr
|DEC|, |LDX|, |CMPX|, |JGE|\hfill\cr
}$
&
$\matrix{
\phantom{0.}3u\cr
\phantom{0.}6u\cr
}$
\cr
}
тАКИМ ОБРАЗОМ, ПРИ КАЖДОМ ПРОСМОТРЕ НА КАЖДУЮ ЗАПИСЬ ЗАТРАЧИВАЕТСЯ 
$12.5$~ЕДИНИЦ ВРЕМЕНИ, И ОБЩЕЕ ВРЕМЯ РАБОТЫ АСИМПТОТИЧЕСКИ ПРИБЛИЖАЕТСЯ 
К~$12.5N\log_2 N$ КАК В СРЕДНЕМ, ТАК И В НАИХУДШЕМ СЛУЧАЕ. эТО МЕДЛЕННЕЕ 
БЫСТРОЙ СОРТИРОВКИ И НЕ НАСТОЛЬКО ЛУЧШЕ ВРЕМЕНИ РАБОТЫ ПИРАМИДАЛЬНОЙ 
СОРТИРОВКИ, ЧТОБЫ ОПРАВДАТЬ ВДВОЕ БОЛЬШИЙ РАСХОД ПАМЯТИ, ТАК КАК 
АСИМПТОТИЧЕСКОЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ~5.2.3H РАВНО $16N\log_2 N$.

%% 198

в АЛГОРИТМЕ~N ГРАНИЦЫ МЕЖДУ ОТРЕЗКАМИ ПОЛНОСТЬЮ ОПРЕДЕЛЯЮТСЯ 
"СТУПЕНЬКАМИ ВНИЗ". тАКОЙ ПОДХОД ОБЛАДАЕТ ТЕМ ВОЗМОЖНЫМ ПРЕИМУЩЕСТВОМ, 
ЧТО ИСХОДНЫЕ ФАЙЛЫ С ПРЕОБЛАДАНИЕМ ВОЗРАСТАЮЩЕГО \emph{ИЛИ УБЫВАЮЩЕГО} 
РАСПОЛОЖЕНИЯ ЭЛЕМЕНТОВ МОГУТ ОБРАБАТЫВАТЬСЯ ОЧЕНЬ БЫСТРО, НО ПРИ ЭТОМ 
ЗАМЕДЛЯЕТСЯ ОСНОВНОЙ ЦИКЛ ВЫЧИСЛЕНИЙ. вМЕСТО ПРОВЕРОК СТУПЕНЕК ВНИЗ МОЖНО 
ПРИНУДИТЕЛЬНО УСТАНОВИТЬ ДЛИНУ ОТРЕЗКОВ, СЧИТАЯ, ЧТО ВСЕ 
ОТРЕЗКИ ИСХОДНОГО ФАЙЛА ИМЕЮТ ДЛИНУ~$1$, ПОСЛЕ ПЕРВОГО ПРОСМОТРА 
ВСЕ ОТРЕЗКИ (КРОМЕ, ВОЗМОЖНО, ПОСЛЕДНЕГО) ИМЕЮТ ДЛИНУ 2, \dots, 
ПОСЛЕ $k\hbox{-Гo}$ ПРОСМОТРА ВСЕ ОТРЕЗКИ (КРОМЕ, ВОЗМОЖНО, 
ПОСЛЕДНЕГО) ИМЕЮТ ДЛИНУ~$2^k$. в ОТЛИЧИЕ ОТ "ЕСТЕСТВЕННОГО" СЛИЯНИЯ В 
АЛГОРИТМЕ~N ТАКОЙ СПОСОБ НАЗЫВАЕТСЯ \emph{ПРОСТЫМ} ДВУХПУТЕВЫМ СЛИЯНИЕМ.

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

\alg S.(сОРТИРОВКА ПРОСТЫМ ДВУХПУТЕВЫМ СЛИЯНИЕМ.) кАК И В АЛГОРИТМЕ~N, ПРИ 
СОРТИРОВКЕ ЗАПИСЕЙ $R_1$, \dots, $R_N$ ИСПОЛЬЗУЮТСЯ ДВЕ ОБЛАСТИ ПАМЯТИ.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $s\asg0$, $p\asg1$. 
(сМЫСЛ ПЕРЕМЕННЫХ~$s$, $i$, $j$, $k$, $l$, $d$ СМ. В АЛГОРИТМЕ~N. зДЕСЬ 
$p$---РАЗМЕР ВОЗРАСТАЮЩИХ ОТРЕЗКОВ, КОТОРЫЕ БУДУТ СЛИВАТЬСЯ ВО ВРЕМЯ 
ТЕКУЩЕГО ПРОСМОТРА; $q$ И~$r$---КОЛИЧЕСТВА НЕСЛИТЫХ ЭЛЕМЕНТОВ В ОТРЕЗКАХ.)

\st[пОДГОТОВКА К ПРОСМОТРУ.] еСЛИ $s=0$, ТО УСТАНОВИТЬ $i\asg1$, 
$j\asg N$, $k\asg N$, $l\asg2N+1$; ЕСЛИ $s=1$, ТО УСТАНОВИТЬ $i\asg N+1$, 
$j\asg2N$, $k\asg0$, $l\asg N+1$. зАТЕМ УСТАНОВИТЬ $d\asg1$, $q\asg p$, 
$r\asg p$.

\st[сРАВНЕНИЕ $K_i:K_j$.] еСЛИ $K_i>K_j$, ТО ПЕРЕЙТИ К ШАГУ~\stp{8}.

\st[пЕРЕСЫЛКА $R_i$] уСТАНОВИТЬ $k\asg k+d$, $R_k\asg R_i$.

\st[кОНЕЦ ОТРЕЗКА?] уСТАНОВИТЬ $i\asg i+1$, $q\asg q-1$. еСЛИ $q > 0$, ТО 
ВОЗВРАТИТЬСЯ К ШАГУ~\stp{3}.

\st[пЕРЕСЫЛКА $R_j$.] уСТАНОВИТЬ $k\asg k+d$. зАТЕМ, ЕСЛИ $k=l$, ПЕРЕЙТИ К 
ШАГУ~\stp{13}; В ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ
$R_k\asg R_j$.

\st[кОНЕЦ ОТРЕЗКА?] уСТАНОВИТЬ $j\asg j-1$, $r\asg r-1$. 
еСЛИ~$r>0$, ВОЗВРАТИТЬСЯ К ШАГУ \stp{6}; В ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ
К ШАГУ \stp{12}.

\st [пЕРЕСЫЛКА $R_j$.] уСТАНОВИТЬ $k\asg k+d$, $R_k\asg R_j$ 

\st[кОНЕЦ ОТРЕЗКА?] уСТАНОВИТЬ $j\asg j-1$, $r\asg r-1$. 
еСЛИ~$r> 0$, ТО ВОЗВРАТИТЬСЯ К ШАГУ~\stp{3}. 
\st[пЕРЕСЫЛКА $R_i$.] уСТАНОВИТЬ $k\asg k+d$. зАТЕМ, ЕСЛИ $k=l$,
ПЕРЕЙТИ К ШАГУ~\stp{13}; В ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ
$R_k\asg R_i$.
%% 199
\st[кОНЕЦ ОТРЕЗКА?] уСТАНОВИТЬ $i\asg i+1$, $q\asg q-1$. еСЛИ $q > 0$, ТО 
ВОЗВРАТИТЬСЯ К ШАГУ \stp{10}.

\st[пЕРЕКЛЮЧЕНИЕ НАПРАВЛЕНИЯ.] уСТАНОВИТЬ $q\asg p$, $r\asg p$, $d\asg -d$ 
И ВЗАИМОЗАМЕНИТЬ $k\xchg l$. вОЗВРАТИТЬСЯ К ШАГУ \stp{3}.

\st[пЕРЕКЛЮЧЕНИЕ ОБЛАСТЕЙ.] уСТАНОВИТЬ $p\asg p+p$. еСЛИ $p<N$, ТО 
УСТАНОВИТЬ $s\asg 1-s$ И ВОЗВРАТИТЬСЯ К~\stp{2}. в ПРОТИВНОМ СЛУЧАЕ 
СОРТИРОВКА ЗАВЕРШЕНА; ЕСЛИ $s=0$, ТО УСТАНОВИТЬ
$$
(R_1, \ldots, R_n)\asg (R_{N+1}, \ldots, R_{2N}).
$$
(нЕЗАВИСИМО ОТ РАСПРЕДЕЛЕНИЯ ИСХОДНОГО ФАЙЛА ПОСЛЕДНЕЕ КОПИРОВАНИЕ БУДЕТ 
ВЫПОЛНЕНО ТОГДА И ТОЛЬКО ТОГДА, КОГДА ЗНАЧЕНИЕ~$\ceil{\log_2 N}$ НЕЧЕТНО. 
тАК ЧТО МОЖНО ЗАРАНЕЕ ПРЕДСКАЗАТЬ ПОЛОЖЕНИЕ ОТСОРТИРОВАННОГО ФАЙЛА, И 
КОПИРОВАНИЕ, КАК ПРАВИЛО, НЕ ТРЕБУЕТСЯ.)
\algend

{\def|{\mskip\thinmuskip\vert\hidewidth}
 \catcode`\!=\active
 \def!{\mskip\thinmuskip\vrule width 0.5mm\hidewidth}
\htable{тАБЛИЦА 2}%
{сОРТИРОВКА ПРОСТЫМ ДВУХПУТЕВЫМ СЛИЯНИЕМ}
{\bskip$#$\bskip&&\bskip$#$\bskip\cr
503|& 087|& 512|& 061|& 908|& 170|& 897|& 275!& 653|& 426|& 154|& 509|& 612|& 677|& 765|& 703\cr
503 & 703|& 512 & 677|& 509 & 908|& 426 & 897!& 653 & 275 & 170 & 154|& 612 & 061|& 765 & 087\cr
087 & 503 & 703 & 765|& 154 & 170 & 509 & 908!& 897 & 653 & 426 & 275|& 677 & 612 & 512 & 061\cr
061 & 087 & 503 & 512 & 612 & 677 & 703 & 765!& 908 & 897 & 653 & 509 & 426 & 275 & 170 & 154\cr
061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908\cr
}
}

пРИМЕР РАБОТЫ АЛГОРИТМА СМ. В ТАБЛ.~2. дОВОЛЬНО УДИВИТЕЛЬНО, ЧТО ЭТОТ 
МЕТОД СПРАВЕДЛИВ И ТОГДА, КОГДА $N$ НЕ ЯВЛЯЕТСЯ СТЕПЕНЬЮ~2; СЛИВАЕМЫЕ 
ОТРЕЗКИ НЕ ВСЕ ИМЕЮТ ДЛИНУ $2^k$, ТЕМ НЕ МЕНЕЕ НИКАКИХ ЯВНЫХ МЕР 
ПРЕДОСТОРОЖНОСТИ НА СЛУЧАЙ ТАКИХ ИСКЛЮЧЕНИЙ НЕ ПРЕДУСМОТРЕНО! (сМ. 
УПР.~8.) пРОВЕРКИ СТУПЕНЕК ВНИЗ ЗАМЕНЕНЫ УМЕНЬШЕНИЕМ ПЕРЕМЕННЫХ~$q$ И~$r$ 
И ПРОВЕРКОЙ НА РАВЕНСТВО НУЛЮ. бЛАГОДАРЯ ЭТОМУ ВРЕМЯ РАБОТЫ НА МАШИНЕ 
\MIX\ АСИМПТОТИЧЕСКИ ПРИБЛИЖАЕТСЯ К $11N\log_2 N$~ЕДИНИЦАМ, ЧТО НЕСКОЛЬКО 
ЛУЧШЕ ЗНАЧЕНИЯ, КОТОРОГО НАМ УДАЛОСЬ ДОБИТЬСЯ В АЛГОРИТМЕ~N.

нА ПРАКТИКЕ ИМЕЕТ СМЫСЛ КОМБИНИРОВАТЬ АЛГОРИТМ~S С ПРОСТЫМИ ВСТАВКАМИ; 
ВМЕСТО ПЕРВЫХ ЧЕТЫРЕХ ПРОСМОТРОВ АЛГОРИТМА~S МОЖНО ПРОСТЫМИ ВСТАВКАМИ 
ОТСОРТИРОВАТЬ ГРУППЫ, СКАЖЕМ, ИЗ 16~ЭЛЕМЕНТОВ, ИСКЛЮЧИВ ТАКИМ ОБРАЗОМ 
ДОВОЛЬНО РАСТОЧИТЕЛЬНЫЕ ВСПОМОГАТЕЛЬНЫЕ ОПЕРАЦИИ, СВЯЗАННЫЕ СО СЛИЯНИЕМ 
КОРОТКИХ ФАЙЛОВ. кАК МЫ УЖЕ ВИДЕЛИ В СЛУЧАЕ БЫСТРОЙ СОРТИРОВКИ, 
ТАКОЕ КОМБИНИРОВАНИЕ МЕТОДОВ НЕ ВЛИЯЕТ/НА АСИМПТОТИЧЕСКОЕ ВРЕМЯ РАБОТЫ, НО 
ДАЕТ ТЕМ НЕ МЕНЕЕ, НЕМАЛУЮ ВЫГОДУ.

рАССМОТРИМ ТЕПЕРЬ АЛГОРИТМЫ~N И~S С ТОЧКИ ЗРЕНИЯ СТРУКТУР ДАННЫХ. пОЧЕМУ 
НАМ НЕОБХОДИМА ПАМЯТЬ ПОД $2N$, А НЕ ПОД $N$
%% 200
~ЗАПИСЕЙ? пРИЧИНА ОТНОСИТЕЛЬНО ПРОСТА: МЫ РАБОТАЕМ С ЧЕТЫРЬМЯ СПИСКАМИ 
ПЕРЕМЕННОГО РАЗМЕРА (ДВА "ВХОДНЫХ СПИСКА" И ДВА "ВЫХОДНЫХ СПИСКА" В КАЖДОМ 
ПРОСМОТРЕ); ПРИ ЭТОМ ДЛЯ КАЖДОЙ ПАРЫ ПОСЛЕДОВАТЕЛЬНО РАСПРЕДЕЛЕННЫХ 
СПИСКОВ МЫ ПОЛЬЗУЕМСЯ СТАНДАРТНЫМ ПОНЯТИЕМ "ВСТРЕЧНОГО РОСТА", 
ОБСУЖДАВШИМСЯ В (П.~2.2.2. нО В ЛЮБОЙ МОМЕНТ ВРЕМЕНИ ПОЛОВИНА ПАМЯТИ НЕ 
ИСПОЛЬЗУЕТСЯ, И ПОСЛЕ НЕКОТОРОГО РАЗМЫШЛЕНИЯ СТАНОВИТСЯ ЯСНО, ЧТО В 
ДЕЙСТВИТЕЛЬНОСТИ, ДЛЯ НАШИХ ЧЕТЫРЕХ СПИСКОВ СЛЕДОВАЛО БЫ ВОСПОЛЬЗОВАТЬСЯ 
\emph{СВЯЗАННЫМ} РАСПРЕДЕЛЕНИЕМ ПАМЯТИ. еСЛИ К КАЖДОЙ ИЗ $N$~ЗАПИСЕЙ 
ДОБАВИТЬ ПОЛЕ СВЯЗИ, ТО ВСЕ НЕОБХОДИМОЕ МОЖНО ПРОДЕЛАТЬ, ПОЛЬЗУЯСЬ 
АЛГОРИТМАМИ СЛИЯНИЯ, КОТОРЫЕ ПРОИЗВОДЯТ ПРОСТЫЕ МАНИПУЛЯЦИИ СО СВЯЗЯМИ И 
СОВСЕМ НЕ ПЕРЕМЕЩАЮТ САМИ ЗАПИСИ. дОБАВЛЕНИЕ $N$~ПОЛЕЙ СВЯЗИ, КАК 
ПРАВИЛО, ВЫГОДНЕЕ, ЧЕМ ДОБАВЛЕНИЕ ПРОСТРАНСТВА ПАМЯТИ ЕЩЕ ПОД 
$N$~ЗАПИСЕЙ, А ОТКАЗАВШИСЬ ОТ ПЕРЕМЕЩЕНИЯ ЗАПИСЕЙ, МЫ МОЖЕМ 
ТАКЖЕ СЭКОНОМИТЬ И ВРЕМЯ. иТАК, НАМ НУЖНО РАССМОТРЕТЬ АЛГОРИТМ, ПОДОБНЫЙ 
СЛЕДУЮЩЕМУ.

\alg L.(сОРТИРОВКА ПОСРЕДСТВОМ СЛИЯНИЯ СПИСКОВ.) пРЕДПОЛАГАЕТСЯ, ЧТО 
ЗАПИСИ $R_1$, \dots, $R_N$ СОДЕРЖАТ КЛЮЧИ $K_1$,~\dots, $K_N$ И "ПОЛЯ 
СВЯЗИ" $L_1$,~\dots, $L_N$, В КОТОРЫХ МОГУТ ХРАНИТЬСЯ ЧИСЛА ОТ~$-(N+1)$ 
ДО~$(N+1)$. в НАЧАЛЕ И В КОНЦЕ ФАЙЛА ИМЕЮТСЯ ИСКУССТВЕННЫЕ ЗАПИСИ~$R_0$ 
И~$R_{N+1}$ С ПОЛЯМИ СВЯЗИ~$L_0$ И~$L_{N+1}$ эТОТ АЛГОРИТМ СОРТИРОВКИ 
СПИСКОВ УСТАНАВЛИВАЕТ ПОЛЯ СВЯЗИ ТАКИМ ОБРАЗОМ, ЧТО ЗАПИСИ ОКАЗЫВАЮТСЯ 
СВЯЗАННЫМИ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. пОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ $L_0$ 
УКАЗЫВАЕТ НА ЗАПИСЬ С НАИМЕНЬШИМ КЛЮЧОМ; ПРИ $1\le k \le N$ СВЯЗЬ~$L_k$ 
УКАЗЫВАЕТ НА ЗАПИСЬ, СЛЕДУЮЩУЮ ЗА~$R_k$, А ЕСЛИ $R_k$---ЗАПИСЬ С 
НАИБОЛЬШИМ КЛЮЧОМ, ТО $L_k=0$. (сМ. ФОРМУЛЫ (5.2.1--9).)

в ПРОЦЕССЕ ВЫПОЛНЕНИЯ ЭТОГО АЛГОРИТМА ЗАПИСИ~$R_0$ И~$R_{N+1}$ СЛУЖАТ 
"ГОЛОВАМИ" ДВУХ ЛИНЕЙНЫХ СПИСКОВ, ПОДСПИСКИ КОТОРЫХ В ДАННЫЙ МОМЕНТ 
СЛИВАЮТСЯ. оТРИЦАТЕЛЬНАЯ СВЯЗЬ ОЗНАЧАЕТ КОНЕЦ ПОДСПИСКА, О КОТОРОМ 
ИЗВЕСТНО, ЧТО ОН УПОРЯДОЧЕН; НУЛЕВАЯ СВЯЗЬ ОЗНАЧАЕТ КОНЕЦ ВСЕГО СПИСКА. 
пРЕДПОЛАГАЕТСЯ, ЧТО $N\ge 2$.

чЕРЕЗ "$\abs{L_s}\asg p$" ОБОЗНАЧЕНА ОПЕРАЦИЯ "ПРИСВОИТЬ $L_s$ 
ЗНАЧЕНИЕ~$p$ ИЛИ~$-p$, СОХРАНИВ ПРЕЖНИЙ ЗНАК $L_s$". тАКАЯ 
ОПЕРАЦИЯ ЛЕГКО РЕАЛИЗУЕТСЯ НА МАШИНЕ \MIX, НО, К СОЖАЛЕНИЮ, ЭТО НЕ ТАК ДЛЯ 
БОЛЬШИНСТВА эвм. нЕТРУДНО ИЗМЕНИТЬ АЛГОРИТМ, ЧТОБЫ ПОЛУЧИТЬ СТОЛЬ ЖЕ 
ЭФФЕКТИВНЫЙ МЕТОД И ДЛЯ БОЛЬШИНСТВА ДРУГИХ МАШИН.

\st[пОДГОТОВИТЬ ДВА СПИСКА.] уСТАНОВИТЬ $L_0\asg1$, $L_{N+1}\asg2$,
 $L_i\asg -(i+2)$ ПРИ~$l\le i\le N-2$ И~$L_{N-1}\asg L_N\asg0$. (мЫ 
СОЗДАЛИ ДВА СПИСКА, СОДЕРЖАЩИЕ СООТВЕТСТВЕННО ЗАПИСИ~$R_1$, $R_3$, $R_5$,
~\dots{} И~$R_2$, $R_4$, $R_6$,~\dots{}; ОТРИЦАТЕЛЬНЫЕ СВЯЗИ ГОВОРЯТ О ТОМ,
 ЧТО КАЖДЫЙ УПОРЯДОЧЕННЫЙ "ПОДСПИСОК" СОСТОИТ ВСЕГО ЛИШЬ ИЗ ОДНОГО 
ЭЛЕМЕНТА. дРУГОЙ СПОСОБ ВЫПОЛНИТЬ ЭТОТ ШАГ,
%% 201
ИЗВЛЕКАЯ ПОЛЬЗУ ИЗ УПОРЯДОЧЕННОСТИ, КОТОРАЯ МОГЛА ПРИСУТСТВОВАТЬ В 
ИСХОДНЫХ ДАННЫХ, СМ. В УПР.~12.)

\st[нАЧАТЬ НОВЫЙ ПРОСМОТР.] уСТАНОВИТЬ $s\asg 0$, $t\asg N+1$, $p\asg L_s$,
 $q\asg L_t$. еСЛИ $q=0$, ТО РАБОТА АЛГОРИТМА ЗАВЕРШЕНА. (пРИ КАЖДОМ 
ПРОСМОТРЕ $p$ И~$q$ ПРОБЕГАЮТ ПО СПИСКАМ, КОТОРЫЕ ПОДВЕРГАЮТСЯ СЛИЯНИЮ; 
$s$ ОБЫЧНО УКАЗЫВАЕТ НА ПОСЛЕДНЮЮ ОБРАБОТАННУЮ ЗАПИСЬ ТЕКУЩЕГО ПОДСПИСКА,
 a $t$---НА КОНЕЦ ТОЛЬКО ЧТО ВЫВЕДЕННОГО ПОДСПИСКА.)

\st[сРАВНИТЬ $K_p:K_q$.] еСЛИ $K_p>K_q$, ТО ПЕРЕЙТИ К~\stp{6}.

\st[пРОДВИНУТЬ $p$.] уСТАНОВИТЬ $\abs{L_s}\asg p$, $s\asg p$, $p\asg L_p$. 
еСЛИ $p>0$, ТО ВОЗВРАТИТЬСЯ К~\stp{3}.

\st[зАКОНЧИТЬ ПОДСПИСОК.] уСТАНОВИТЬ $L_s\asg q$, $s\asg t$. 
зАТЕМ УСТАНОВИТЬ $t\asg q$ И~$q\asg L_q$ ОДИН ИЛИ БОЛЕЕ РАЗ, ПОКА 
НЕ СТАНЕТ $q\le 0$, ПОСЛЕ ЧЕГО ПЕРЕЙТИ К~\stp{8}.

\st[пРОДВИНУТЬ $q$.] (шАГИ \stp{6} И~\stp{7} ДВОЙСТВЕННЫ ПО 
ОТНОШЕНИЮ К~\stp{4} И~\stp{5}.) уСТАНОВИТЬ $\abs{L_s}\asg q$, $s\asg q$, 
$q\asg L_q$. еСЛИ~$q>0$, ТО ВОЗВРАТИТЬСЯ К~\stp{3}.

\st[зАКОНЧИТЬ ПОДСПИСОК.] уСТАНОВИТЬ $L_s\asg p$, $s\asg t$. 
зАТЕМ УСТАНОВИТЬ $t\asg p$ И~$p\asg L_p$ ОДИН ИЛИ БОЛЕЕ РАЗ, ПОКА НЕ СТАНЕТ~$p>0$.

\st[кОНЕЦ ПРОСМОТРА?] (к ЭТОМУ МОМЕНТУ $p\le 0$ И~$q\le 0$, ТАК КАК ОБА 
УКАЗАТЕЛЯ ПРОДВИНУЛИСЬ ДО КОНЦА СООТВЕТСТВУЮЩИХ ПОДСПИСКОВ.) 
уСТАНОВИТЬ~$p\asg -p$,  $q\asg -q$. еСЛИ $q=0$, 
ТО УСТАНОВИТЬ~$\abs{L_s}\asg p$, $\abs{L_t}\asg 0$, И ВОЗВРАТИТЬСЯ 
К~\stp{2}; В ПРОТИВНОМ СЛУЧАЕ ВОЗВРАТИТЬСЯ К~\stp{3}.
\algend

пРИМЕР РАБОТЫ ЭТОГО АЛГОРИТМА ПРИВЕДЕН В ТАБЛ.~3, В КОТОРОЙ ПОКАЗАНЫ 
СВЯЗИ К МОМЕНТУ ВЫПОЛНЕНИЯ ШАГА~L2. пО ОКОНЧАНИИ РАБОТЫ АЛГОРИТМА МОЖНО, 
ПОЛЬЗУЯСЬ МЕТОДОМ ИЗ УПР.~5.2--12, ПЕРЕРАЗМЕСТИТЬ ЗАПИСИ ТАК, ЧТОБЫ ИХ 
КЛЮЧИ БЫЛИ УПОРЯДОЧЕНЫ. мОЖНО ЗАМЕТИТЬ ИНТЕРЕСНУЮ АНАЛОГИЮ МЕЖДУ СЛИЯНИЕМ 
СПИСКОВ И СЛОЖЕНИЕМ РАЗРЕЖЕННЫХ МНОГОЧЛЕНОВ (СМ. АЛГОРИТМ 2.2.4а).
{\catcode`\!=\active\def!#1.{\omit\hfill$#1$\hfill}
\htable{тАБЛИЦА 3}%
{сОРТИРОВКА ПОСРЕДСТВОМ СЛИЯНИЯ СПИСКОВ}%
{\bskip$#$\bskip&&\hfill$#$\bskip\cr
j   &!0.& !1.& !2.& !3.& !4.& !5.& !6.& !7.& !8.& !9.&!10.&!11.&!12.&!13.&!14.&!15.&!16.&!17.\cr
K_i & - & 503& 087& 512& 061& 908& 170& 897& 275& 653& 426& 154& 509& 612& 677& 765& 703&  -\cr
L_j & 1 &  -3&  -4&  -5&  -6&  -7&  -8&  -9& -10& -11& -12& -13& -14& -15& -16&   0&   0&  2\cr
L_j & 2 &  -6&   1&  -8&   3& -10&   5& -11&   7& -13&   9&  12& -16&  14&   0&   0&  15&  4\cr
L_j & 4 &   3&   1& -11&   2& -13&   8&   5&   7&   0&  12&  10&   9&  14&  16&   0&  15&  6\cr
L_j & 4 &   3&   6&   7&   2&   0&   8&   5&   1&  14&  12&  10&  13&   9&  16&   0&  15& 11\cr
L_j & 4 &  12&  11&  13&   2&   0&   8&   5&  10&  14&   1&   6&   3&   9&  16&   7&  15&  0\cr
}
}

нАПИШЕМ ТЕПЕРЬ \MIX-ПРОГРАММУ ДЛЯ АЛГОРИТМА~L, ЧТОБЫ ВЫЯСНИТЬ, СТОЛЬ ЛИ 
ВЫГОДНО ОПЕРИРОВАТЬ СПИСКАМИ С ТОЧКИ ЗРЕНИЯ ВРЕМЕНИ, КАК И С ТОЧКИ ЗРЕНИЯ ПРОСТРАНСТВА?
%%202
\prog L.(сОРТИРОВКА ПОСРЕДСТВОМ СЛИЯНИЯ СПИСКОВ.) дЛЯ УДОБСТВА 
ПРЕДПОЛАГАЕТСЯ, ЧТО ЗАПИСИ ЗАНИМАЮТ ОДНО СЛОВО, ПРИЧЕМ $L_j$ ХРАНИТСЯ В 
ПОЛЕ $(0:2)$, А $K_j$---В ПОЛЕ $(3:5)$ ЯЧЕЙКИ $|INPUT|+j$;
ЗНАЧЕНИЯ РЕГИСТРОВ: $|rI1|\equiv p$, $|rI2|\equiv q$, $|rI3|\equiv s$, 
$|rI4|\equiv t$ $|rA|\equiv R_q$; $N\ge 2$.
\code
L    & EQU  & 0:2          &       & оПРЕДЕЛЕНИЕ ИМЕН ПОЛЕЙ.
ABSL & EQU  & 1:2
KEY  & EQU  & 3:5
START& ENT1 & N-2          & 1     & L1. пОДГОТОВИТЬ ДВА СПИСКА.
     & ENNA & 2,1          & N-2
     & STA  & INPUT,1(L)   & N-2   & $L_i\asg -(i+2)$.
     & DEC1 & 1            & N-2
     & J1P  & *-3          & N-2   & $N-2\ge i>0$.
     & ENTA & 1            & 1
     & STA  & INPUT(L)     & 1     & $L_0\asg 1$.
     & ENTA & 2            & 1
     & STA  & INPUT+N+1(L) & 1     & $L_{N+1}\asg2$.
     & STZ  & INPUT+ N-1(L)& 1     & $L_{N-1}\asg 0$.
     & STZ  & INPUT +N(L)  & 1     & $L_N\asg 0$.
     & JMP  & L2           & 1     & к L2.
L3Q  & LDA  & INPUT,2      & C''+B'& L3. сРАВНИТЬ $K_p:K_q$.
L3P  & CMPA & INPUT,1(KEY) & C
     & JL   & L6           & C     & к L6, ЕСЛИ $K_q<K_p$.
L4   & ST1  & INPUT,3(ABSL)& C'    & L4. пРОДВИНУТЬ~$p$. $\abs{L_s}\asg p$.
     & ENT3 & 0,1          & C'    & $s-p$.
     & LD1  & INPUT, 1(L)  & C'    & $p\asg L_p$
     & J1P  & L3P          & C'    & к L3, ЕСЛИ~$p>0$.
L5   & ST2  & INPUT,3(L)   & B'    & L5. зАКОНЧИТЬ ПОДСПИСОК. $L_s\asg q$.
     & ENT3 & 0,4          & B'    & $s\asg t$.
     & ENT4 & 0,2          & D'    & $t\asg q$.
     & LD2  & INPUT,2(L)   & D'    & $q\asg L_q$.
     & J2P  & *-2          & D'    & пОВТОРИТЬ, ЕСЛИ $q>0$.
     & JMP  & L8           & B'    & к L8
L6   & ST2  & INPUT,3(ABSL)& C''   & L6. пРОДВИНУТЬ~$q$. $\abs{L_s}\asg q$.
     & ENT3 & 0,2          & C''   & $s\asg q$.
     & LD2  & INPUT,2(L)   & C''   & $q\asg L_q$.
     & J2P  & L3Q          & C''   & к L3, ЕСЛИ~$q>0$.
L7   & ST1  & INPUT,3(L)   & B''   & L7. зАКОНЧИТЬ ПОДСПИСОК. $L_s\asg p$.
     & ENT3 & 0,4          & B''   & $s\asg t$.
     & ENT4 & 0,1          & D''   & $t\asg p$.
     & LD1  & INPUT, 1(L)  & D''   & $p\asg L_p$.
     & J1P  & *-2          & D''   & пОВТОРИТЬ, ЕСЛИ~$p>0$.
L8   & ENN1 & 0,1          & B     & L8. кОНЕЦ ПРОСМОТРА? $p\asg -p$.
     & ENN2 & 0,2          & B     & $q\asg -q$.
     & J2NZ & L3Q          & B     & к L3, ЕСЛИ $q\ne0$.
     & ST1  & INPUT,3(ABSL)& A     & $\abs{L_s}\asg p$.
     & STZ  & INPUT,4(ABSL)& A     & $\abs{L_t}\asg0$.
%%203
L2   & ENT3 & 0            & A+1   & L2. нАЧАТЬ НОВЫЙ ПРОСМОТР, $s\asg0$.
     & ENT4 & N+1          & A+1   & $t\asg N+1$.
     & LD1  & INPUT (L)    & A+1   & $p\asg L_s$.
     & LD2  & INPUT+N+1(L) & A+1   & $q\asg L_t$.
     & J2NZ & L3Q          & A+1   & к L3, ЕСЛИ $q \ne 0$.
\endcode

вРЕМЯ РАБОТЫ ЭТОЙ ПРОГРАММЫ МОЖНО ОЦЕНИТЬ ПРИ ПОМОЩИ МЕТОДОВ, КОТОРЫМИ МЫ 
УЖЕ НЕ РАЗ ПОЛЬЗОВАЛИСЬ (СМ. УПР.~13, 14);
В СРЕДНЕМ ОНО РАВНО ПРИБЛИЗИТЕЛЬНО $(10N \log_2 N+4.92N)$~ЕДИНИЦ С 
НЕБОЛЬШИМ СТАНДАРТНЫМ ОТКЛОНЕНИЕМ ПОРЯДКА $\sqrt{N}$. в УПР.~15 ПОКАЗАНО, 
ЧТО ЗА СЧЕТ НЕКОТОРОГО УДЛИНЕНИЯ ПРОГРАММЫ МОЖНО СОКРАТИТЬ ВРЕМЯ ПРИМЕРНО 
ДО~$9N\log_2N$.

иТАК, В СЛУЧАЕ ВНУТРЕННЕГО СЛИЯНИЯ СВЯЗАННОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ ИМЕЕТ 
БЕССПОРНЫЕ ПРЕИМУЩЕСТВА ПЕРЕД ПОСЛЕДОВАТЕЛЬНЫМ РАСПРЕДЕЛЕНИЕМ: ТРЕБУЕТСЯ 
МЕНЬШЕ ПАМЯТИ, И ПРОГРАММА РАБОТАЕТ НА 10--20\% БЫСТРЕЕ. аНАЛОГИЧНЫЕ 
АЛГОРИТМЫ ОПУБЛИКОВАНЫ л.~дЖ.~вУДРАМОМ [{\sl IBM Systems J.\/}, {\bf 8} 
(1969), 189--203] И а.~д.~вУДАЛЛОМ [{\sl сОТР. J.\/}, {\bf 13} (1970), 110--111].

\excercises
\ex[20] оБОБЩИТЕ АЛГОРИТМ~M НА \emph{$k\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ} ИСХОДНЫХ 
ФАЙЛОВ $x_{i1}\le \ldots\le x_{im_i}$ ПРИ $i=1,$ 2, \dots, $k$.

\ex[м24] сЧИТАЯ, ЧТО ВСЕ $\perm{m+n}{m}$ ВОЗМОЖНЫХ РАСПОЛОЖЕНИЙ 
$m$~ЭЛЕМЕНТОВ~$x$ СРЕДИ $n$~ЭЛЕМЕНТОВ~$y$ РАВНОВЕРОЯТНЫ, НАЙДИТЕ 
МАТЕМАТИЧЕСКОЕ ОЖИДАНИЕ И СТАНДАРТНОЕ ОТКЛОНЕНИЕ ЧИСЛА ВЫПОЛНЕНИИ ШАГА~M2 
В АЛГОРИТМЕ~M. чЕМУ РАВНЫ МАКСИМАЛЬНОЕ И МИНИМАЛЬНОЕ ЗНАЧЕНИЯ ЭТОЙ ВЕЛИЧИНЫ?

\rex[20] \exhead(иЗМЕНЕНИЕ.) дАНЫ ЗАПИСИ $R_1$,~\dots, $R_M$ И~$R'_1$,
~\dots, $R'_N$, КЛЮЧИ КОТОРЫХ РАЗЛИЧНЫ И УПОРЯДОЧЕНЫ, 
Т.~Е.~$K_1<\ldots<K_M$ И $K'_1<\ldots<K'_N$. 
кАК НУЖНО ИЗМЕНИТЬ АЛГОРИТМ~M, ЧТОБЫ В 
РЕЗУЛЬТАТЕ СЛИЯНИЯ ПОЛУЧАЛСЯ ФАЙЛ, В КОТОРОМ ОТСУТСТВУЮТ ЗАПИСИ~$R_i$ 
ПЕРВОГО ФАЙЛА, ЕСЛИ ВО ВТОРОМ ФАЙЛЕ ТОЖЕ ЕСТЬ ЗАПИСЬ С ТАКИМ ЖЕ КЛЮЧОМ?

\ex[21] в ТЕКСТЕ ОТМЕЧЕНО, ЧТО СОРТИРОВКУ СЛИЯНИЕМ МОЖНО РАССМАТРИВАТЬ КАК 
ОБОБЩЕНИЕ СОРТИРОВКИ ВСТАВКАМИ. пОКАЖИТЕ, ЧТО МЕТОД СЛИЯНИЙ 
ИМЕЕТ НЕПОСРЕДСТВЕННОЕ ОТНОШЕНИЕ И К ВЫБОРУ ИЗ ДЕРЕВА (ВОСПОЛЬЗУЙТЕСЬ В 
КАЧЕСТВЕ ИЛЛЮСТРАЦИИ РИС.~23).

\rex[21] дОКАЖИТЕ, ЧТО В ШАГАХ~N6 И~N10 ПЕРЕМЕННЫЕ~$i$ И~$j$ НЕ МОГУТ 
БЫТЬ РАВНЫ. (пОЭТОМУ В ЭТИХ ШАГАХ ПРОВЕРКА НА СЛУЧАЙ ВОЗМОЖНОГО ПЕРЕХОДА К~N13 НЕОБЯЗАТЕЛЬНА.)

\ex[22] нАЙДИТЕ ТАКУЮ ПЕРЕСТАНОВКУ $K_1 K_2 \ldots K_{16}$ 
МНОЖЕСТВА~$\{1, 2, \ldots, 16\}$, ЧТО
$$
\displaylines{
  K_2>K_3, K_4>K_5, K_6>K_7, K_8>K_9,\cr
  K_{10}<K_{11}, K_{12}<K_{13}, K_{14}<K_{15},\cr
}
$$
КОТОРАЯ ТЕМ НЕ МЕНЕЕ БУДЕТ ОТСОРТИРОВАНА ПРИ ПОМОЩИ АЛГОРИТМА~N ВСЕГО 
ЗА ДВА ПРОСМОТРА. (тАК КАК В ИСКОМОЙ ПЕРЕСТАНОВКЕ ИМЕЕТСЯ НЕ МЕНЕЕ 
ВОСЬМИ ОТРЕЗКОВ, ТО МЫ МОГЛИ БЫ ОЖИДАТЬ, ЧТО ПОСЛЕ ПЕРВОГО ПРОСМОТРА 
ОСТАНУТСЯ ПО МЕНЬШЕЙ МЕРЕ ЧЕТЫРЕ ОТРЕЗКА, ПОСЛЕ ВТОРОГО ПРОСМОТРА---ДВА 
ОТРЕЗКА, И СОРТИРОВКА, КАК ПРАВИЛО, НЕ ЗАВЕРШИТСЯ РАНЬШЕ ОКОНЧАНИЯ 
ТРЕТЬЕГО ПРОСМОТРА. кАКИМ ЖЕ ОБРАЗОМ МОЖНО ОБОЙТИСЬ ВСЕГО ДВУМЯ ПРОСМОТРАМИ?)

%%204
\ex[16] нАЙДИТЕ ТОЧНУЮ ФОРМУЛУ, ВЫРАЖАЮЩУЮ ЧИСЛО ПРОСМОТРОВ АЛГОРИТМА~S 
В ВИДЕ ФУНКЦИИ ОТ~N.

\ex[22] пРЕДПОЛАГАЕТСЯ, ЧТО ВО ВРЕМЯ РАБОТЫ АЛГОРИТМА ПЕРЕМЕННЫЕ~$q$ 
И~$r$Г ПРЕДСТАВЛЯЮТ ДЛИНЫ НЕСЛИТЫХ ЧАСТЕЙ ОТРЕЗКОВ, ОБРАБАТЫВАЕМЫХ В 
ДАННЫЙ МОМЕНТ; В НАЧАЛЕ РАБОТЫ -КАК~$q$, ТАК И~$r$ УСТАНАВЛИВАЮТСЯ 
РАВНЫМИ~$p$, В ТО ВРЕМЯ КАК ОТРЕЗКИ НЕ ВСЕГДА ИМЕЮТ ТАКУЮ ДЛИНУ. пОЧЕМУ ЖЕ 
АЛГОРИТМ ТЕМ НЕ МЕНЕЕ РАБОТАЕТ ПРАВИЛЬНО?

\ex [24] нАПИШИТЕ \MIX-ПРОГРАММУ ДЛЯ АЛГОРИТМА~S. вЫРАЗИТЕ 
ЧАСТОТУ ВЫПОЛНЕНИЯ КАЖДОЙ КОМАНДЫ ЧЕРЕЗ ВЕЛИЧИНЫ, ПОДОБНЫЕ $A$, $B'$, 
$B''$, $C'$, \dots В ПРОГРАММЕ~L.

\ex[25] (д. а. бЕЛЛ.) пОКАЖИТЕ, ЧТО ПРОСТОЕ ДВУХПУТЕВОЕ СЛИЯНИЕ ФАЙЛОВ С 
ПОСЛЕДОВАТЕЛЬНО РАСПОЛОЖЕННЫМИ ЭЛЕМЕНТАМИ МОЖНО ВЫПОЛНИТЬ, ИМЕЯ ВСЕГО 
${3\over2}N$~ЯЧЕЕК ПАМЯТИ, А НЕ $2N$, КАК В АЛГОРИТМЕ~S.

\ex[21] яВЛЯЕТСЯ ЛИ АЛГОРИТМ~L АЛГОРИТМОМ "УСТОЙЧИВОЙ" СОРТИРОВКИ?

\rex[22] иЗМЕНИТЕ ШАГ~L1 АЛГОРИТМА~L ТАК, ЧТОБЫ ДВУХПУТЕВОЕ СЛИЯНИЕ СТАЛО 
"ЕСТЕСТВЕННЫМ", ИЗВЛЕКАЯ ПОЛЬЗУ ИЗ НАЛИЧИЯ ВОЗРАСТАЮЩИХ ОТРЕЗКОВ В 
ИСХОДНОМ ФАЙЛЕ. (в ЧАСТНОСТИ, ЕСЛИ ИСХОДНЫЕ ДАННЫЕ УЖЕ УПОРЯДОЧЕНЫ, 
ТО ШАГ~L2 ЗАВЕРШИТ РАБОТУ АЛГОРИТМА СРАЗУ ЖЕ ПОСЛЕ ВЫПОЛНЕНИЯ 
ИЗМЕНЕННОГО ВАМИ ШАГА~L1.)

\rex[м34] пРОАНАЛИЗИРУЙТЕ СРЕДНЕЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ~L ПОДОБНО ТОМУ, 
КАК МЫ АНАЛИЗИРОВАЛИ ДРУГИЕ АЛГОРИТМЫ В ЭТОЙ ГЛАВЕ. дАЙТЕ ТОЛКОВАНИЕ 
ВЕЛИЧИНАМ~$A$, $B$, $B'$, \dots И ОБоЯСНИТЕ, КАК ВЫЧИСЛИТЬ ИХ ТОЧНЫЕ 
СРЕДНИЕ ЗНАЧЕНИЯ. сКОЛЬКО ВРЕМЕНИ ЗАТРАТИТ ПРОГРАММА~L НА СОРТИРОВКУ 
16~ЧИСЕЛ В ТАБЛ.~3?

\ex[м24] пУСТЬ ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ ЧИСЛА~$N$---ЭТО 
$2^{e_1}+2^{e_2}+\cdots+2^{e_t}$, ГДЕ $e_1>e_2>\ldots>e_t\ge0$, $t\ge1$. 
дОКАЖИТЕ, ЧТО МАКСИМАЛЬНОЕ ЧИСЛО СРАВНЕНИЙ
КЛЮЧЕЙ, ВЫПОЛНЯЕМЫХ АЛГОРИТМОМ~L, РАВНО 
$1-2^{e_t}+\sum{1\le k\le t}(e_k+k-1)2^{e_k}$.

\ex[20] еСЛИ ПРОМОДЕЛИРОВАТЬ ВРУЧНУЮ РАБОТУ АЛГОРИТМА~L, ТО ОБНАРУЖИТСЯ, 
ЧТО В НЕМ ИНОГДА ВЫПОЛНЯЮТСЯ ЛИШНИЕ ОПЕРАЦИИ; ПРИМЕРНО В ПОЛОВИНЕ 
СЛУЧАЕВ НЕ НУЖНЫ ПРИСВАИВАНИЯ $\abs{L_s}\asg p$, $\abs{L_s}\asg q$ В 
ШАГАХ~L4 И~L6, ПОСКОЛЬКУ МЫ ИМЕЕМ $L_s=p$ (ИЛИ~$q$) ВСЯКИЙ РАЗ, КОГДА 
ВОЗВРАЩАЕМСЯ ИЗ ШАГА~L4 (ИЛИ L6) К~L3. кАК УЛУЧШИТЬ ПРОГРАММУ~L, 
ИЗБАВИВШИСЬ ОТ ЭТИХ  ЛИШНИХ ПРИСВАИВАНИИ?

\ex[28] рАЗРАБОТАЙТЕ АЛГОРИТМ СЛИЯНИЯ СПИСКОВ, ПОДОБНЫЙ АЛГОРИТМУ~L, НО 
ОСНОВАННЫЙ НА ТРЕХПУТЕВОМ СЛИЯНИИ.

\ex[20] (дЖ.~мАК-кАРТИ.) пУСТЬ ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ ЧИСЛА~$N$ ТАКОЕ ЖЕ, 
КАК В УПР.~14, И ПРЕДПОЛОЖИМ, ЧТО ДАНО $N$~ЗАПИСЕЙ, ОРГАНИЗОВАННЫХ В $t$
УПОРЯДОЧЕННЫХ ПОДФАЙЛОВ, ИМЕЮЩИХ РАЗМЕРЫ СООТВЕТСТВЕННО 
$2^{e_1}$, $2^{e_2}$, \dots, $2^{e_t}$.
пОКАЖИТЕ, КАК МОЖНО СОХРАНИТЬ ТАКОЕ СОСТОЯНИЕ ПРИ ДОБАВЛЕНИИ 
$(N+1)\hbox{-Й}$ ЗАПИСИ И~$N\asg N+1$. (пОЛУЧЕННЫЙ АЛГОРИТМ МОЖНО НАЗВАТЬ 
"ОПЕРАТИВНОЙ" СОРТИРОВКОЙ СЛИЯНИЕМ.)

\ex[40] (м.~а.~кРОНРОД.) мОЖНО ЛИ ОТСОРТИРОВАТЬ ФАЙЛ ИЗ $N$~ЗАПИСЕЙ,
 СОДЕРЖАЩИЙ ВСЕГО ДВА ОТРЕЗКА:
$$
K_1\le\ldots\le K_M\quad\hbox{И}\quad K_{M+1}\le\ldots\le K_N,
$$
зА $O(N)$ ОПЕРАЦИЙ В ПАМЯТИ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ, \emph{ИСПОЛЬЗУЯ ЛИШЬ 
НЕБОЛЬШОЕ ДОПОЛНИТЕЛЬНОЕ ПРОСТРАНСТВО ПАМЯТИ ФИКСИРОВАННОГО РАЗМЕРА}, НЕ 
ЗАВИСЯЩЕГО ОТ~$M$ И~$N$? (вСЕ АЛГОРИТМЫ СЛИЯНИЯ, ОПИСАННЫЕ В ЭТОМ ПУНКТЕ,
 ИСПОЛЬЗУЮТ ДОПОЛНИТЕЛЬНОЕ ПРОСТРАНСТВО ПАМЯТИ, ПРОПОРЦИОНАЛЬНОЕ~$N$.)

\ex[26] рАССМОТРИМ ЖЕЛЕЗНОДОРОЖНЫЙ РАЗоЕЗД С $n$~"СТЕКАМИ", КАК ПОКАЗАНО 
НА РИС.~31 ПРИ $n=5$; ТАКОЙ РАЗоЕЗД ИМЕЕТ НЕКОТОРОЕ ОТНОШЕНИЕ К 
АЛГОРИТМАМ СОРТИРОВКИ С $n$~ПРОСМОТРАМИ. в УПР.~С~2.2.1--2 ПО~2.2.1--5 
МЫ РАССМОТРЕЛИ РАЗоЕЗДЫ С ОДНИМ СТЕКОМ. вЫ ВИДЕЛИ, ЧТО ЕСЛИ С ПРАВОГО 
КОНЦА ПОСТУПАЕТ $N$~ВАГОНОВ, ТО СЛЕВА МОЖЕТ ПОЯВИТЬСЯ СРАВНИТЕЛЬНО 
НЕБОЛЬШОЕ КОЛИЧЕСТВО ИЗ $N$~ВСЕВОЗМОЖНЫХ ПЕРЕСТАНОВОК ЭТИХ ВАГОНОВ.
%% 205

пРЕДПОЛОЖИМ, ЧТО В РАЗоЕЗД С $n$~СТЕКАМИ СПРАВА ПОСТУПАЕТ 
$2^n$~ВАГОНОВ. дОКАЖИТЕ, ЧТО ПРИ ПОМОЩИ ПОДХОДЯЩЕЙ ПОСЛЕДОВАТЕЛЬНОСТИ 
ОПЕРАЦИЙ СЛЕВА \emph{МОЖНО ПОЛУЧИТЬ} ЛЮБУЮ ИЗ~$2^n!$ ВСЕВОЗМОЖНЫХ 
ПЕРЕСТАНОВОК ЭТИХ ВАГОНОВ. (кАЖДЫЙ СТЕК ДОСТАТОЧНО ВЕЛИК, И ПРИ 
НЕОБХОДИМОСТИ В НЕГО МОЖНО ПОМЕСТИТЬ ВСЕ ВАГОНЫ).

\ex[47] в ОБОЗНАЧЕНИЯХ УПР.~2.2.1--4 ПРИ ПОМОЩИ РАЗоЕЗДОВ С 
$n$~СТЕКАМИ МОЖНО ПОЛУЧИТЬ НЕ БОЛЕЕ $a^n_N$~ПЕРЕСТАНОВОК $N$~ЭЛЕМЕНТОВ; 
СЛЕДОВАТЕЛЬНО, ДЛЯ
\picture{рИС. 31.жЕЛЕЗНОДОРОЖНЫЙ РАЗоЕЗД С ПЯТЬЮ "СТЕКАМИ".}
ПОЛУЧЕНИЯ ВСЕХ $N!$~ПЕРЕСТАНОВОК ТРЕБУЕТСЯ НЕ МЕНЕЕ $\log N!/\log 
a_N\approx \log_4 N$~СТЕКОВ. в УПР.~19 ПОКАЗАНО, ЧТО НУЖНО НЕ БОЛЕЕ 
$\ceil{\log_2 N}$~СТЕКОВ. кАКОВА ИСТИННАЯ СКОРОСТЬ РОСТА НЕОБХОДИМОГО 
ЧИСЛА СТЕКОВ ПРИ $N\to\infty$?

\ex[23] (э.~дЖ.~сМИТ.) оБоЯСНИТЕ, КАК МОЖНО ОБОБЩИТЬ АЛГОРИТМ~L, ЧТОБЫ ОН, 
ПОМИМО СОРТИРОВКИ, ВЫЧИСЛЯЛ ТАКЖЕ ЧИСЛО \emph{ИНВЕРСИЙ} В ИСХОДНОЙ ПЕРЕСТАНОВКЕ.

\subsubchap{рАСПРЕДЕЛЯЮЩАЯ СОРТИРОВКА} % 5.2.5
мЫ ПОДХОДИМ ТЕПЕРЬ К ИНТЕРЕСНОМУ КЛАССУ МЕТОДОВ СОРТИРОВКИ, КОТОРЫЙ, КАК 
ПОКАЗАНО В П.~5.4.7, ПО СУЩЕСТВУ, ПРЯМО \emph{ПРОТИВОПОЛОЖЕН} СЛИЯНИЮ. 
чИТАТЕЛЯМ, ЗНАКОМЫМ С ПЕРФОКАРТОЧНЫМ ОБОРУДОВАНИЕМ, ХОРОШО ИЗВЕСТНА 
ЭФФЕКТИВНАЯ ПРОЦЕДУРА, ПРИМЕНЯЕМАЯ В МАШИНАХ ДЛЯ СОРТИРОВКИ КАРТ И 
ОСНОВАННАЯ НА СРАВНЕНИИ ЦИФР КЛЮЧЕЙ; ТУ ЖЕ ИДЕЮ МОЖНО ПРИСПОСОБИТЬ И 
ДЛЯ ПРОГРАММИРОВАНИЯ. оНА ОБЩЕИЗВЕСТНА ПОД НАЗВАНИЯМИ "ПОРАЗРЯДНАЯ 
СОРТИРОВКА", "ЦИФРОВАЯ СОРТИРОВКА" ИЛИ "КАРМАННАЯ СОРТИРОВКА".

пРЕДПОЛОЖИМ, НАМ НУЖНО ОТСОРТИРОВАТЬ КОЛОДУ ИЗ 52~ИГРАЛЬНЫХ КАРТ. 
оПРЕДЕЛИМ УПОРЯДОЧЕНИЕ ПО СТАРШИНСТВУ (ДОСТОИНСТВУ) КАРТ В МАСТИ
$$
т<2<3<4<5<6<7<8<9<10<в<д<к,
$$
А ТАКЖЕ ПО МАСТИ
$$
\clubsuit<\diamondsuit<\heartsuit<\spadesuit
$$
оДНА КАРТА ПРЕДШЕСТВУЕТ ДРУГОЙ, ЕСЛИ ЛИБО (i)~ОНА МЛАДШЕ ПО МАСТИ, ЛИБО 
(ii)~МАСТИ ОБЕИХ КАРТ ОДИНАКОВЫ, НО ОНА МЛАДШЕ
%%206
ПО ДОСТОИНСТВУ. (эТО ЧАСТНЫЙ СЛУЧАЙ \emph{ЛЕКСИКОГРАФИЧЕСКОГО} 
УПОРЯДОЧЕНИЯ НА МНОЖЕСТВЕ УПОРЯДОЧЕННЫХ ПАР ПРЕДМЕТОВ; СР.~С~УПР.~5--2.) 
тАКИМ ОБРАЗОМ,
$$
т\clubsuit<2\clubsuit<\cdots<к\clubsuit<
т\diamondsuit<\cdots<д\spadesuit< к\spadesuit
$$

мЫ МОГЛИ БЫ ОТСОРТИРОВАТЬ КАРТЫ ОДНИМ ИЗ ОБСУЖДАВШИХСЯ РАНЕЕ МЕТОДОВ; ЛЮДИ,
 КАК ПРАВИЛО, ПОЛЬЗУЮТСЯ СПОСОБОМ, ПО СУТИ АНАЛОГИЧНЫМ ОБМЕННОЙ 
ПОРАЗРЯДНОЙ СОРТИРОВКЕ. еСТЕСТВЕННО ОТСОРТИРОВАТЬ КАРТЫ СНАЧАЛА ПО ИХ 
МАСТИ, РАЗЛОЖИВ ИХ В ЧЕТЫРЕ СТОПКИ, А ЗАТЕМ ПЕРЕКЛАДЫВАТЬ КАРТЫ ВНУТРИ 
КАЖДОЙ СТОПКИ ДО ТЕХ ПОР, ПОКА ОНИ НЕ БУДУТ УПОРЯДОЧЕНЫ ПО ДОСТОИНСТВУ.

нО СУЩЕСТВУЕТ БОЛЕЕ БЫСТРЫЙ СПОСОБ! сНАЧАЛА РАЗЛОЖИТЬ КАРТЫ В 13~СТОПОК 
ЛИЦЕВОЙ СТОРОНОЙ ВВЕРХ ПО ИХ ДОСТОИНСТВУ. зАТЕМ СОБРАТЬ ВСЕ СТОПКИ ВМЕСТЕ: 
СНИЗУ ТУЗЫ, ЗАТЕМ ДВОЙКИ, ТРОЙКИ И Т. Д. И СВЕРХУ КОРОЛИ (ЛИЦЕВОЙ СТОРОНОЙ 
ВВЕРХ). пЕРЕВЕРНУТЬ КОЛОДУ РУБАШКАМИ ВВЕРХ И СНОВА РАЗЛОЖИТЬ, НА 
ЭТОТ РАЗ В ЧЕТЫРЕ СТОПКИ ПО МАСТИ. сЛОЖИВ ВМЕСТЕ ПОЛУЧЕННЫЕ СТОПКИ ТАК, 
ЧТОБЫ ВНИЗУ БЫЛИ ТРЕФЫ, ЗАТЕМ БУБНЫ, ЧЕРВИ И ПИКИ, ПОЛУЧИМ УПОРЯДОЧЕННУЮ 
КОЛОДУ КАРТ.

тА ЖЕ ИДЕЯ ГОДИТСЯ И ДЛЯ СОРТИРОВКИ ЧИСЛОВЫХ И БУКВЕННЫХ ДАННЫХ. пОЧЕМУ ЖЕ 
ОНА ПРАВИЛЬНА? пОТОМУ ЧТО (В НАШЕМ ПРИМЕРЕ С ИГРАЛЬНЫМИ КАРТАМИ), ЕСЛИ 
ДВЕ КАРТЫ ПРИ ПОСЛЕДНЕМ РАСКЛАДЕ ПОПАЛИ В РАЗНЫЕ СТОПКИ, ТО ОНИ ИМЕЮТ 
РАЗНЫЕ МАСТИ, ТАК ЧТО КАРТА С МЕНЬШЕЙ МАСТЬЮ МЛАДШЕ. еСЛИ ЖЕ КАРТЫ 
ОДНОЙ МАСТИ, ТО ОНИ УЖЕ НАХОДЯТСЯ В НУЖНОМ ПОРЯДКЕ БЛАГОДАРЯ 
ПРЕДВАРИТЕЛЬНОЙ СОРТИРОВКЕ. иНАЧЕ ГОВОРЯ, ПРИ ВТОРОМ РАСКЛАДЕ В КАЖДОЙ 
ИЗ ЧЕТЫРЕХ СТОПОК КАРТЫ БУДУТ РАСПОЛОЖЕНЫ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ. эТО 
ДОКАЗАТЕЛЬСТВО МОЖНО ОБОБЩИТЬ И ПОКАЗАТЬ, ЧТО ТАКИМ СПОСОБОМ МОЖНО 
ОТСОРТИРОВАТЬ ЛЮБОЕ МНОЖЕСТВО С ЛЕКСИКОГРАФИЧЕСКИМ УПОРЯДОЧЕНИЕМ; 
ПОДРОБНОСТИ СМ. В УПР.~5--2 (В НАЧАЛЕ ГЛАВЫ).

тОЛЬКО ЧТО ОПИСАННЫЙ МЕТОД СОРТИРОВКИ СРАЗУ НЕ ОЧЕВИДЕН, И НЕ ЯСНО, КТО ЖЕ 
ПЕРВЫЙ ОБНАРУЖИЛ, ЧТО ОН ТАК УДОБЕН. в БРОШЮРЕ НА 19~СТРАНИЦАХ ПОД 
НАЗВАНИЕМ "The Inventory Simplified", ОПУБЛИКОВАННОЙ ОТДЕЛЕНИЕМ ФИРМЫ IBM 
Tabulating Machines Company В 1923~Г., ПРЕДСТАВЛЕН ИНТЕРЕСНЫЙ ЦИФРОВОЙ 
МЕТОД ВЫЧИСЛЕНИЯ СУММ ПРОИЗВЕДЕНИЙ НА СОРТИРОВАЛЬНОЙ МАШИНЕ. пУСТЬ, 
НАПРИМЕР, НУЖНО ПЕРЕМНОЖИТЬ ДВА ЧИСЛА, ПРОБИТЫХ СООТВЕТСТВЕННО В 
КОЛОНКАХ~1--10 И В КОЛОНКАХ~23--25, И ВЫЧИСЛИТЬ СУММУ ТАКИХ ПРОИЗВЕДЕНИЙ 
ДЛЯ БОЛЬШОГО ЧИСЛА КАРТ. тОГДА СНАЧАЛА МОЖНО ОТСОРТИРОВАТЬ КАРТЫ ПО 
КОЛОНКЕ~25 И НАЙТИ ПРИ ПОМОЩИ СЧЕТНО-АНАЛИТИЧЕСКОЙ МАШИНЫ ВЕЛИЧИНЫ $a_1$, 
$a_2$,~\dots $a_9$, ГДЕ $a_k$---СУММА ЧИСЕЛ ИЗ КОЛОНОК 1--10 ПО ВСЕМ КАРТОЧКАМ, 
%%207
НА КОТОРЫХ В КОЛОНКЕ~25 ПРОБИТА ЦИФРА~$k$. зАТЕМ МОЖНО ОТСОРТИРОВАТЬ 
КАРТЫ ПО КОЛОНКЕ~24 И НАЙТИ АНАЛОГИЧНЫЕ СУММЫ $b_1$, $b_2$,~\dots, $b_9$, 
А ПОТОМ ПО КОЛОНКЕ~23, ПОЛУЧИВ ВЕЛИЧИНЫ~$c_1$, $c_2$,~\dots, $c_9$. лЕГКО 
ВИДЕТЬ, ЧТО ИСКОМАЯ СУММА ПРОИЗВЕДЕНИЙ РАВНА
$$
a_1+2a_2+\cdots+9a_9+10b_1+20b_2+\cdots+90b_9+
100c_1+200c_2+\cdots+900c_9.
$$
тАКОЙ ПЕРФОКАРТОЧНЫЙ МЕТОД ТАБУЛИРОВАНИЯ ЕСТЕСТВЕННЫМ ОБРАЗОМ ПРИВОДИТ К 
ИДЕЕ ПОРАЗРЯДНОЙ СОРТИРОВКИ "СНАЧАЛА-ПО-МЛАДШЕЙ-ЦИФРЕ", ТАК ЧТО, 
ПО-ВИДИМОМУ, ОНА ВПЕРВЫЕ СТАЛА ИЗВЕСТНА ОПЕРАТОРАМ ЭТИХ МАШИН. пЕРВАЯ 
ОПУБЛИКОВАННАЯ ССЫЛКА НА ЭТОТ МЕТОД СОДЕРЖИТСЯ В РАННЕЙ РАБОТЕ 
л.~дЖ.~кОМРИ, ПОСВЯЩЕННОЙ ОБСУЖДЕНИЮ ПЕРФОКАРТОЧНОГО ОБОРУДОВАНИЯ 
[Transactions of the Office Machinery Users' Assoc., Ltd. (1929), 25--37,
 ОСОБЕННО СТР. 28].

чТОБЫ ВЫПОЛНИТЬ ПОРАЗРЯДНУЮ СОРТИРОВКУ С ПОМОЩЬЮ эвм, НЕОБХОДИМО РЕШИТЬ, 
КАК ПРЕДСТАВЛЯТЬ СТОПКИ. пУСТЬ ИМЕЕТСЯ $M$~СТОПОК; МОЖНО БЫЛО БЫ ВЫДЕЛИТЬ 
$M$~ОБЛАСТЕЙ ПАМЯТИ И ПЕРЕСЫЛАТЬ КАЖДУЮ ИСХОДНУЮ ЗАПИСЬ В 
СООТВЕТСТВУЮЩУЮ ОБЛАСТЬ. нО ЭТО РЕШЕНИЕ НАС НЕ УДОВЛЕТВОРЯЕТ, ПОТОМУ ЧТО В 
КАЖДОЙ ОБЛАСТИ ДОЛЖНО БЫТЬ ДОСТАТОЧНО МЕСТА ДЛЯ ХРАНЕНИЯ $N$~ЭЛЕМЕНТОВ, 
И ТОГДА ПОТРЕБУЕТСЯ ПРОСТРАНСТВО ПОД $(M+1)N$~ЗАПИСЕЙ. тАКАЯ ЧРЕЗМЕРНАЯ 
ПОТРЕБНОСТЬ В ПАМЯТИ ЗАСТАВЛЯЛА БОЛЬШИНСТВО  ПРОГРАММИСТОВ ОТКАЗЫВАТЬСЯ ОТ 
ПРИМЕНЕНИЯ ПОРАЗРЯДНОЙ СОРТИРОВКИ НА ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ, ПОКА 
X.~сЬЮВОРД [ДИПЛОМНАЯ РАБОТА, M.I.т. Digital Computer Laboratory 
Report R-232 (Cambridge Mass: 1954), 25--28] НЕ ПОКАЗАЛ, ЧТО ТОГО 
ЖЕ ЭФФЕКТА МОЖНО ДОБИТЬСЯ, ИМЕЯ В РАСПОРЯЖЕНИИ ПРОСТРАНСТВО ВСЕГО ПОД 
$2N$~ЗАПИСЕЙ И $M$~СЧЕТЧИКОВ. сДЕЛАВ ОДИН ПРЕДВАРИТЕЛЬНЫЙ ПРОСМОТР 
ДАННЫХ, МОЖНО ПРОСТО ПОСЧИТАТЬ, СКОЛЬКО ЭЛЕМЕНТОВ ПОПАДЕТ В КАЖДУЮ 
ОБЛАСТЬ; ЭТО ДАСТ НАМ ВОЗМОЖНОСТЬ ТОЧНО РАСПРЕДЕЛИТЬ ПАМЯТЬ ПОД СТОПКИ. мЫ 
УЖЕ ПРИМЕНЯЛИ ЭТУ ИДЕЮ ПРИ РАСПРЕДЕЛЯЮЩЕЙ СОРТИРОВКЕ (АЛГОРИТМ 5.2D).

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

еСЛИ У НАС ИМЕЕТСЯ ДЕСЯТИЧНАЯ МАШИНА, А КЛЮЧИ---12-РАЗРЯДНЫЕ ЧИСЛА И ЕСЛИ 
$N$~ВЕСЬМА ВЕЛИКО, ТО МОЖНО ВЫБРАТЬ $M=1000$ (СЧИТАЯ ТРИ ДЕСЯТИЧНЫЕ ЦИФРЫ 
ЗА ОДНУ В СИСТЕМЕ СЧИСЛЕНИЯ С ОСНОВАНИЕМ 1000); НЕЗАВИСИМО ОТ ВЕЛИЧИНЫ~$N$ 
СОРТИРОВКА БУДЕТ
%% 208
ВЫПОЛНЕНА ЗА ЧЕТЫРЕ ПРОСМОТРА. аНАЛОГИЧНО, ЕСЛИ БЫ ИМЕЛАСЬ ДВОИЧНАЯ МАШИНА,
 А КЛЮЧИ---40-БИТОВЫЕ ДВОИЧНЫЕ ЧИСЛА, ТО МОЖНО ПОЛОЖИТЬ $M=1024$ И ТАКЖЕ 
ЗАВЕРШИТЬ СОРТИРОВКУ ЗА ЧЕТЫРЕ ПРОСМОТРА. фАКТИЧЕСКИ КАЖДЫЙ ПРОСМОТР 
СОСТОИТ ИЗ ТРЕХ ЧАСТЕЙ (ПОДСЧЕТ, РАСПРЕДЕЛЕНИЕ ПАМЯТИ, ПЕРЕМЕЩЕНИЕ); 
фРЭНД [{\sl JACM,\/} {\bf 3} (1956), 151] 
ПРЕДЛОЖИЛ КОМБИНИРОВАТЬ ДВА ИЗ ЭТИХ ТРЕХ ДЕЙСТВИЙ, ДОБАВИВ ЕЩЕ 
$M$~ЯЧЕЕК: НАКАПЛИВАТЬ ЗНАЧЕНИЯ СЧЕТЧИКОВ ДЛЯ $(k+1)\hbox{-ГО}$ ПРОСМОТРА 
ОДНОВРЕМЕННО С ПЕРЕМЕЩЕНИЕМ ВО ВРЕМЯ $k\hbox{-ГО}$ ПРОСМОТРА.

в ТАБЛ.~1 ПОКАЗАНО ПРИМЕНЕНИЕ ПОРАЗРЯДНОЙ СОРТИРОВКИ К НАШИМ 16~КЛЮЧАМ ПРИ 
$M=10$. пРИ ТАКИХ МАЛЫХ~$N$ ПОРАЗРЯДНАЯ СОРТИРОВКА, КАК ПРАВИЛО, НЕ 
ОСОБЕННО ПОЛЕЗНА, ТАК ЧТО ЭТОТ МАЛЕНЬКИЙ ПРИМЕР ПРЕДНАЗНАЧЕН ГЛАВНЫМ 
ОБРАЗОМ ДЛЯ ТОГО, ЧТОБЫ ПРОДЕМОНСТРИРОВАТЬ ДОСТАТОЧНОСТЬ МЕТОДА, А НЕ ЕГО 
ЭФФЕКТИВНОСТЬ.

{
\def\subtable#1{
\noalign{
\halign{
##\hfill\bskip&&\bskip\hfill$##$\cr
#1
}}
}
\htable{тАБЛИЦА 1}{пОРАЗРЯДНАЯ СОРТИРОВКА}{
#\hfill\bskip&&\bskip$#$\cr
оБЛАСТЬ ВВОДА:           & 503 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 & 154 & 509 & 612 & 677 & 765 & 703 \cr
\subtable{
сЧЕТЧИКИ ДЛЯ МЛАДШИХ ЦИФР:           & 1& 1& 2& 3& 1& 2& 1& 3& 1& 1\cr
сООТВЕТСТВУЮЩЕЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ:& 1& 2& 4& 7& 8&10&11&14&15&16\cr
}
вСПОМОГАТЕЛЬНАЯ ОБЛАСТЬ: & 170 & 061 & 512 & 612 & 503 & 653 & 703 & 154 & 275 & 765 & 426 & 087 & 897 & 677 & 908 & 509 \cr
\subtable{
сЧЕТЧИКИ ДЛЯ СРЕДНИХ ЦИФР:           & 4& 2& 1& 0& 0& 2& 2& 3& 1& 1\cr
сООТВЕТСТВУЮЩЕЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ:& 4& 6& 7& 7& 7& 9&11&14&15&16\cr
}
оБЛАСТЬ ВВОДА;           & 503 & 703 & 908 & 509 & 512 & 612 & 426 & 653 & 154 & 061 & 765 & 170 & 275 & 677 & 087 & 897 \cr
\subtable{
сЧЕТЧИКИ ДЛЯ СТАРШИХ ЦИФР:           & 2& 2& 1& 0& 1& 3& 3& 2& 1& 1\cr
сООТВЕТСТВУЮЩЕЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ:& 2& 4& 5& 5& 6& 9&12&14&15&16\cr
}
вСПОМОГАТЕЛЬНАЯ ОБЛАСТЬ: & 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
}
}

иСКУШЕННЫЙ "СОВРЕМЕННЫЙ" ЧИТАТЕЛЬ ЗАМЕТИТ, ОДНАКО, ЧТО ИДЕЯ СЧЕТЧИКОВ ДЛЯ 
РАСПРЕДЕЛЕНИЯ ПАМЯТИ ПРИВЯЗАНА К "СТАРОМОДНЫМ" ПОНЯТИЯМ О 
ПОСЛЕДОВАТЕЛЬНОМ ПРЕДСТАВЛЕНИИ ДАННЫХ;
НАМ ЖЕ ИЗВЕСТНО, ЧТО СПЕЦИАЛЬНО ДЛЯ РАБОТЫ С МНОЖЕСТВОМ ТАБЛИЦ 
ПЕРЕМЕННОЙ ДЛИНЫ ПРИДУМАНО \emph{СВЯЗАННОЕ} РАСПРЕДЕЛЕНИЕ. пОЭТОМУ ДЛЯ 
ПОРАЗРЯДНОЙ СОРТИРОВКИ ЕСТЕСТВЕННО БУДЕТ ВОСПОЛЬЗОВАТЬСЯ СВЯЗАННЫМИ 
СТРУКТУРАМИ ДАННЫХ. тАК КАК КАЖДАЯ СТОПКА ПРОСМАТРИВАЕТСЯ ПОСЛЕДОВАТЕЛЬНО, 
ТО ВСЕ, ЧТО НАМ НУЖНО,--- ИМЕТЬ ПРИ КАЖДОМ ЭЛЕМЕНТЕ ОДНУ-ЕДИНСТВЕННУЮ ССЫЛКУ 
НА СЛЕДУЮЩИЙ ЭЛЕМЕНТ. кРОМЕ ТОГО, НИКОГДА НЕ ПРИДЕТСЯ ПЕРЕМЕЩАТЬ ЗАПИСИ: 
ДОСТАТОЧНО СКОРРЕКТИРОВАТЬ СВЯЗИ---И МОЖНО СМЕЛО ДВИГАТЬСЯ ДАЛЬШЕ ПО 
СПИСКАМ. оБоЕМ НЕОБХОДИМОЙ ПАМЯТИ РАВЕН $(1+\varepsilon)N+2\varepsilon 
M$~ЗАПИСЕЙ, ГДЕ $\varepsilon$---ПРОСТРАНСТВО, ЗАНИМАЕМОЕ ОДНИМ ПОЛЕМ СВЯЗИ. 
дОВОЛЬНО ИНТЕРЕСНЫ ФОРМАЛЬНЫЕ ПОДРОБНОСТИ ЭТОЙ
%%209
ПРОЦЕДУРЫ, ПОСКОЛЬКУ ОНИ ДАЮТ ПРЕКРАСНЫЙ ПРИМЕР ТИПИЧНЫХ МАНИПУЛЯЦИЙ СО 
СТРУКТУРАМИ ДАННЫХ, СОЕДИНЯЮЩИХ В СЕБЕ ПОСЛЕДОВАТЕЛЬНОЕ И СВЯЗАННОЕ 
РАСПРЕДЕЛЕНИЕ ПАМЯТИ.
\picture{рИС. 32. пОРАЗРЯДНАЯ СОРТИРОВКА СПИСКА.}

\alg R.(пОРАЗРЯДНАЯ СОРТИРОВКА СПИСКА.) пРЕДПОЛАГАЕТСЯ, ЧТО КАЖДАЯ ИЗ 
ЗАПИСЕЙ~$R_1$,~\dots, $R_N$ СОДЕРЖИТ ПОЛЕ СВЯЗИ |LINK|, А КЛЮЧИ 
ПРЕДСТАВЛЯЮТ СОБОЙ ПОСЛЕДОВАТЕЛЬНОСТЬ ИЗ $p$~ЭЛЕМЕНТОВ
$$
(a_p, \ldots, a_2, a_1), \quad 0\le a_i<M,
$$
И ОТНОШЕНИЕ ПОРЯДКА---ЛЕКСИКОГРАФИЧЕСКОЕ, Т. Е.
$$
(a_p, \ldots, a_2, a_1)<(b_p, \ldots, b_2, b_1)
$$
ТОГДА И ТОЛЬКО ТОГДА, КОГДА СУЩЕСТВУЕТ ТАКОЙ ИНДЕКС~$j$, $1\le j\le p$, 
ЧТО 
$$
a_i=b_i \rem{ПРИ $i>j$, НО $a_j<b_j$.}
$$
кЛЮЧИ МОЖНО ПРЕДСТАВЛЯТЬ СЕБЕ, В ЧАСТНОСТИ, КАК ЧИСЛА, ЗАПИСАННЫЕ В  
СИСТЕМЕ СЧИСЛЕНИЯ С ОСНОВАНИЕМ~$M$:
$$
a_pM^{p-1}+\cdots+a_2M+a_1,
$$
И В ЭТОМ СЛУЧАЕ ЛЕКСИКОГРАФИЧЕСКОЕ ОТНОШЕНИЕ ПОРЯДКА СООТВЕТСТВУЕТ 
ОБЫЧНОМУ УПОРЯДОЧЕНИЮ МНОЖЕСТВА НЕОТРИЦАТЕЛЬНЫХ ЧИСЕЛ. кЛЮЧИ ТАКЖЕ МОГУТ 
БЫТЬ ЦЕПОЧКАМИ БУКВ АЛФАВИТА И Т. Д.

вО ВРЕМЯ СОРТИРОВКИ ФОРМИРУЮТСЯ $M$~"СТОПОК" ПОДОБНО ТОМУ, КАК ЭТО 
ДЕЛАЕТСЯ В СОРТИРОВАЛЬНОЙ МАШИНЕ ДЛЯ ПЕРФОКАРТ. сТОПКИ ФАКТИЧЕСКИ 
ПРЕДСТАВЛЯЮТ СОБОЙ ОЧЕРЕДИ В СМЫСЛЕ ГЛ.~2, ПОСКОЛЬКУ МЫ СВЯЗЫВАЕМ ИХ 
ВМЕСТЕ ТАКИМ ОБРАЗОМ, ЧТО ОНИ ВСЕГДА ПРОСМАТРИВАЮТСЯ ПО ПРИНЦИПУ "ПЕРВЫМ 
ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ". дЛЯ КАЖДОЙ СТОПКИ ИМЕЮТСЯ ДВЕ 
ПЕРЕМЕННЫЕ-УКАЗАТЕЛИ: $|TOP|[i]$ И~$|BOTM|[i]$, $0\le i<M$, И, КАК И В 
ГЛ.~2, ПРЕДПОЛАГАЕТСЯ, ЧТО
$$
|LINK|(|LOC|(|BOTM|([i])))\equiv|BOTM|[i].
$$
%% 210
\st[цИКЛ ПО~$k$.] вНАЧАЛЕ УСТАНОВИТЬ~$|P|\asg|LOC|(R_N)$, УКАЗАТЕЛЬ НА 
ПОСЛЕДНЮЮ ЗАПИСЬ. зАТЕМ ВЫПОЛНИТЬ ШАГИ С~\stp{2} ПО~\stp{6} ПРИ $k=1$, 2,
~\dots, $p$ (ШАГИ С~\stp{2} ПО~\stp{6} СОСТАВЛЯЮТ ОДИН "ПРОСМОТР") И 
ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА. пЕРЕМЕННАЯ~$|P|$ БУДЕТ УКАЗЫВАТЬ НА ЗАПИСЬ С 
НАИМЕНЬШИМ КЛЮЧОМ, $|LINK|(|P|)$--- НА  ЗАПИСЬ  СО  СЛЕДУЮЩИМ  ПО  ВЕЛИЧИНЕ 
КЛЮЧОМ, $|LINK|(|LINK|(|P|))$---НА СЛЕДУЮЩУЮ И Т.Д.; ПОЛЕ~$|LINK|$
ПОСЛЕДНЕЙ ЗАПИСИ БУДЕТ РАВНО~$\NULL$.

\st[оПУСТОШИТЬ СТОПКИ.] пРИ $0\le i<M$ 
УСТАНОВИТЬ~$|TOP|[i]\asg|LOC|(|BOTM|[i])$ И~$|BOTM|[i]\asg\NULL$.

\st[вЫДЕЛИТЬ $k\hbox{-Ю}$ ЦИФРУ КЛЮЧА.] пУСТЬ $|KEY|(|P|)$---КЛЮЧ ЗАПИСИ, НА 
КОТОРУЮ УКАЗЫВАЕТ~$|P|$,---РАВЕН~$(a_p,~\ldots, a_2, a_1)$; 
УСТАНОВИТЬ~$i\asg a_k$, $k\hbox{-Я}$ МЛАДШАЯ ЦИФРА ЭТОГО КЛЮЧА.

\st[сКОРРЕКТИРОВАТЬ СВЯЗИ.] уСТАНОВИТЬ $|LINK|(|TOP|[i])\asg|P|$, ЗАТЕМ~$|TOP|[i]\asg|P|$.

\st[пЕРЕЙТИ К СЛЕДУЮЩЕЙ ЗАПИСИ.] еСЛИ $k=1$ (ПЕРВЫЙ ПРОСМОТР) И 
ЕСЛИ~$|P|=|LOC|(R_j)$ ПРИ НЕКОТОРОМ~$j\ne1$, ТО 
УСТАНОВИТЬ~$|P|\asg|LOC|(R_{j-1})$ И ВОЗВРАТИТЬСЯ К ШАГУ~\stp{3}. 
еСЛИ $k>1$ (НЕ ПЕРВЫЙ ПРОСМОТР), ТО УСТАНОВИТЬ~$|P|\asg|LINK|(|P|)$ И 
ВОЗВРАТИТЬСЯ К~\stp{3}, ЕСЛИ~$|P|\ne\NULL$.

\st[вЫПОЛНИТЬ АЛГОРИТМ~H.] (тЕПЕРЬ МЫ УЖЕ РАСПРЕДЕЛИЛИ ВСЕ ЭЛЕМЕНТЫ ПО 
СТОПКАМ.) вЫПОЛНИТЬ ПРИВЕДЕННЫЙ НИЖЕ АЛГОРИТМ~H, КОТОРЫЙ СЦЕПЛЯЕТ 
ОТДЕЛЬНЫЕ "СТОПКИ" В ОДИН СПИСОК, ПОДГОТАВЛИВАЯ ИХ К СЛЕДУЮЩЕМУ ПРОСМОТРУ. 
зАТЕМ УСТАНОВИТЬ~$|P|\asg|BOTM|[0]$, УКАЗАТЕЛЬ НА ПЕРВЫЙ 
ЭЛЕМЕНТ ОБоЕДИНЕННОГО СПИСКА. (сМ. УПР.~3.)
\algend
\alg H.(сЦЕПЛЕНИЕ ОЧЕРЕДЕЙ.) иЗ $M$~ДАННЫХ ОЧЕРЕДЕЙ СО СВЯЗЯМИ, 
УДОВЛЕТВОРЯЮЩИМИ СОГЛАШЕНИЯМ АЛГОРИТМА~R, ДАННЫЙ АЛГОРИТМ СОЗДАЕТ ОДНУ 
ОЧЕРЕДЬ, МЕНЯЯ ПРИ ЭТОМ НЕ БОЛЕЕ $M$~СВЯЗЕЙ. в РЕЗУЛЬТАТЕ $|BOTM|[0]$ 
УКАЗЫВАЕТ НА ПЕРВЫЙ ЭЛЕМЕНТ, И СТОПКА~0 ПРЕДШЕСТВУЕТ СТОПКЕ~1, \dots, 
ПРЕДШЕСТВУЕТ СТОПКЕ~$(M-1)$.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $i\asg 0$.

\st[уКАЗАТЕЛЬ НА ВЕРШИНУ СТОПКИ.] уСТАНОВИТЬ $|P|\asg|TOP|[i]$.

\st[сЛЕДУЮЩАЯ СТОПКА.] уВЕЛИЧИТЬ~$i$ НА~1. еСЛИ $i=M$, ТО
УСТАНОВИТЬ~$|LINK|(|P|)\asg\NULL$ И ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА.

\st[сТОПКА ПУСТА?] еСЛИ $|BOTM|[i]=\NULL$, Тo ВОЗВРАТИТЬСЯ К~\stp{з}.

\st[сЦЕПИТЬ СТОПКИ.] уСТАНОВИТЬ $|LINK| (|P|)\asg|BOTM|[i]$. вОЗВРАТИТЬСЯ К~\stp{2}.
\algend

нА РИС.~33 ПОКАЗАНО СОДЕРЖИМОЕ СТОПОК ПОСЛЕ КАЖДОГО ИЗ ТРЕХ ПРОСМОТРОВ, 
ВЫПОЛНЯЕМЫХ ПРИ СОРТИРОВКЕ НАШИХ 16~ЧИСЕЛ С~$M=10$. аЛГОРИТМ~R ОЧЕНЬ 
ПРОСТО ЗАПРОГРАММИРОВАТЬ ДЛЯ МАШИНЫ~\MIX, ЕСЛИ ТОЛЬКО НАЙТИ УДОБНЫЙ, 
СПОСОБ ИЗМЕНЯТЬ ОТ ПРОСМОТРА К ПРОСМОТРУ ДЕЙСТВИЯ В ШАГАХ~R3 И~R5. в 
СЛЕДУЮЩЕЙ
%%211
ПРОГРАММЕ ЭТОГО УДАЛОСЬ ДОБИТЬСЯ, НЕ ЖЕРТВУЯ СКОРОСТЬЮ ВНУТРЕННЕГО 
ЦИКЛА, ПУТЕМ ПРЕДВАРИТЕЛЬНОЙ ЗАПИСИ ДВУХ КОМАНД В ТЕЛО ПРОГРАММЫ. зАМЕТИМ, 
ЧТО $|TOP|[i]$ И~$|BOTM|[i]$ МОЖНО УПАКОВАТЬ В ОДНО СЛОВО.

\picture{рИС. 33.               пОРАЗРЯДНАЯ СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ 
СВЯЗАННОГО РАСПРЕДЕЛЕНИЯ ПАМЯТИ (ПОКАЗАНО СОДЕРЖИМОЕ ВСЕХ ДЕСЯТИ СТОПОК 
ПОСЛЕ КАЖДОГО ПРОСМОТРА).
}
\prog R.(пОРАЗРЯДНАЯ СОРТИРОВКА СПИСКОВ.) пРЕДПОЛАГАЕТСЯ, ЧТО ИСХОДНЫЕ 
КЛЮЧИ В ЯЧЕЙКАХ ОТ~$|INPUT|+1$ ДО~$|INPUT|+N$ СОДЕРЖАТ $p=3$~КОМПОНЕНТЫ 
($a_3$, $a_2$, $a_1$), ХРАНЯЩИЕСЯ СООТВЕТСТВЕННО В ПОЛЯХ $(1:1)$, 
$(2:2)$ И~$(3:3)$. (тАКИМ ОБРАЗОМ, СЧИТАЕТСЯ, ЧТО ЗНАЧЕНИЕ~$M$ МЕНЬШЕ ИЛИ 
РАВНО РАЗМЕРУ БАЙТА МАШИНЫ \MIX.) в ПОЛЕ $(4:5)$ ЗАПИСИ ХРАНИТСЯ 
СВЯЗЬ~|LINK|. пУСТЬ 
$|TOP|[i]\equiv |PILES|+i(l :2)$ И~$|BOTM|[i]\equiv |PILES|+i(4:5)$ ПРИ 
$0\le i<M$. уДОБНО УКАЗЫВАТЬ В СВЯЗИ ПОЛОЖЕНИЕ ОТНОСИТЕЛЬНО ЯЧЕЙКИ |INPUT|,
 ТАК ЧТО $|LOC|(|BOTM|[i])=|PILES|+i- |INPUT|$; ЧТОБЫ ИЗБЕЖАТЬ
%%212
ПОЯВЛЕНИЯ ОТРИЦАТЕЛЬНЫХ СВЯЗЕЙ, НУЖНО РАСПОЛОЖИТЬ ТАБЛИЦУ~|PILES| 
ПОСЛЕ ТАБЛИЦЫ~|INPUT|. зНАЧЕНИЯ ИНДЕКСНЫХ РЕГИСТРОВ: $|rI1|\equiv |P|$, 
$|rI2|\equiv i$,  $|rI3|\equiv 3-k$, $|rI4|\equiv|TOP|[i]$; ВО ВРЕМЯ 
РАБОТЫ АЛГОРИТМА~H $|rI2|\equiv i-M$.
\code
LINK & EQU  & 4:5
TOP  & EQU  & 1:2
START& ENT1 & N  & 1 & R1. цИКЛ ПО $k$. $|P|\asg|LOC|(R_N)$.
     & ENT3 & 2  & 1 & $k\asg 1$.
2H   & ENT2 & M-1& 3 & R2. оПУСТОШИТЬ СТОПКИ.
     & ENTA & PILES-INPUT,2 & 3M & $|LOC|(|BOTM|[i])$
     & STA  & PILES,2 (TOP) & 3M & \hfill$\rasg|TOP|[i]$
     & STZ  & PILES,2(LINK) & 3M & $|BOTM|[i]\asg\NULL$.
     & DEC2 & 1             & 3M
     & J2NN & *-4           & 3M & $M>i\ge 0$.
     & LDA  & R3SW,3        & 3
     & STA  & 3F            & 3  &  иЗМЕНИТЬ КОМАНДЫ
     & LDA  & R5SW,3        & 3  &  ДЛЯ $k$-ГО ПРОСМОТРА.
     & STA  & 5F            & 3
3н   & [LD2 & INPUT, 1(3:3)]&    & R3. вЫДЕЛИТЬ $k$-Ю ЦИФРУ КЛЮЧА.
4H   & LD4  & PILES,2 (TOP) & 3N & R4. сКОРРЕКТИРОВАТЬ СВЯЗИ.
     & ST1  & INPUT,4(LINK) & 3N & $|LINK|(|TOP|[i])\asg|P|$.
     & ST1  & PILES,2(TOP)  & 3N & $|TOP|[i]\asg|P|$.
5H   & [DEC1& 1]            &    & R5. пЕРЕЙТИ К СЛЕДУЮЩЕЙ ЗАПИСИ.
     & J1NZ & 3B            & 3N & к R3, ЕСЛИ ПРОСМОТР ЗАКОНЧЕН.
6H   & ENN2 & м             & 3  & R6. вЫПОЛНИТЬ АЛГОРИТМ н.
     & JMP  & 7F            & 3  & к н2 С $i\asg0$.
R3SW & LD2  & INPUT, 1(1:1) & N  & кОМАНДА ДЛЯ R3 ПРИ $k=3$.
     & LD2  & INPUT, 1(2:2) & N  & кОМАНДА ДЛЯ R3 ПРИ $k=2$.
     & LD2  & INPUT, 1(3:3) & N  & кОМАНДА ДЛЯ R3 ПРИ $k=1$.
R5SW & LD1  & INPUT, 1(LINK)& N  & кОМАНДА ДЛЯ R5 ПРИ $k=3$.
     & LD1  & INPUT, 1(LINK)& N  & кОМАНДА ДЛЯ R5 ПРИ $k=2$.
     & DEC1 & 1             & N  & кОМАНДА ДЛЯ R5 ПРИ $k=1$.
9H   & LDA  & PILES+M, 2(LINK)& 3M-3 & н4.сТОПКА ПУСТА?
     & JAZ  & 8F              & 3M-3 & к    нз,   ЕСЛИ $|вотм|[i]=\NULL$
%%213
     & STA  & INPUT, 1(LINK)  & 3M-3-E & H5. сЦЕПИТЬ СТОПКИ $|LINK|(|P|)\asg|BOTM|[i]$.
7H   & LD1  & PILES+M, 2(TOP) & 3M-E   & H2. уКАЗАТЕЛЬ НА ВЕРШИНУ СТОПКИ.
8H   & INC2 & 1               & 3M     & H3. сЛЕДУЮЩАЯ СТОПКА, $i\asg i+1$.
     & J2NZ & 9B              & 3M     & к н4, ЕСЛИ $i\ne M$.
     & STZ  & INPUT, 1(LINK)  & 3      & $|LINK|(|P|)\asg\NULL$.
     & LD1  & PILES (LINK)    & 3      & $|P|\asg|BOTM|[0]$.
     & DEC3 & 1               & 3
     & J3NN & 2B              & 3      & $1\le k\le 3$
\endcode

вРЕМЯ РАБОТЫ ПРОГРАММЫ~R РАВНО $32N+48M+38-4E$, ГДЕ $N$---ЧИСЛО ИСХОДНЫХ 
ЗАПИСЕЙ, $M$---ОСНОВАНИЕ СИСТЕМЫ СЧИСЛЕНИЯ (ЧИСЛО СТОПОК), А $E$---ЧИСЛО 
ВСТРЕТИВШИХСЯ ПУСТЫХ СТОПОК. сРАВНЕНИЕ С ДРУГИМИ ПРОГРАММАМИ, 
ПОСТРОЕННЫМИ НА ОСНОВЕ АНАЛОГИЧНЫХ ПРЕДПОЛОЖЕНИЙ (ПРОГРАММЫ~5.2.1м, 
5.2.4L), ГОВОРИТ ЯВНО В ПОЛЬЗУ ПРОГРАММЫ~R. вРЕМЯ РАБОТЫ 
$p\hbox{-ПРОХОДНОГО}$ ВАРИАНТА ПРОГРАММЫ~R РАВНО $(11p-1)N+O(pM)$~ЕДИНИЦ; 
КРИТИЧЕСКИЙ ФАКТОР, ВЛИЯЮЩИЙ НА ВРЕМЯ РАБОТЫ,---ВНУТРЕННИЙ ЦИКЛ, КОТОРЫЙ 
СОДЕРЖИТ ПЯТЬ ОБРАЩЕНИЙ К ПАМЯТИ И ОДИН ПЕРЕХОД. дЛЯ ТИПИЧНОЙ 
ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ $M=b^r$ И~$p=\ceil{t/r}$, ГДЕ $t$--- ЧИСЛО ЦИФР В 
КЛЮЧАХ, ПРЕДСТАВЛЕННЫХ В СИСТЕМЕ СЧИСЛЕНИЯ С ОСНОВАНИЕМ~$b$; С РОСТОМ~$r$ 
УБЫВАЕТ~$p$, ТАК ЧТО МОЖНО ВОСПОЛЬЗОВАТЬСЯ НАШИМИ ФОРМУЛАМИ ДЛЯ 
ОПРЕДЕЛЕНИЯ "НАИЛУЧШЕГО" ЗНАЧЕНИЯ~$r$.

еДИНСТВЕННАЯ ПЕРЕМЕННАЯ ВЕЛИЧИНА В ФОРМУЛЕ ВРЕМЕНИ РАБОТЫ---ЭТО $E$---ЧИСЛО 
ПУСТЫХ СТОПОК, ОБНАРУЖЕННЫХ В ШАГЕ н4. пРЕДПОЛОЖИМ, ЧТО ВСЕ 
$M^N$~ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЦИФР $M\hbox{-ИЧНОЙ}$ СИСТЕМЫ СЧИСЛЕНИЯ 
РАВНОВЕРОЯТНЫ. иЗ ИЗУЧЕНИЯ "ПОКЕР-ТЕСТА" В П.~3.3.2D МЫ УМЕЕМ ВЫЧИСЛЯТЬ 
ВЕРОЯТНОСТЬ ТОГО, ЧТО В КАЖДОМ ПРОСМОТРЕ ВСТРЕТИТСЯ РОВНО $M-r$ ПУСТЫХ 
СТОПОК; ОНА РАВНА
$$
{M(M-1)\ldots(M-r+1)\over M^N}\left\{{N\atop r}\right\},
$$
ГДЕ $\left\{{N\atop r}\right\}$---ЧИСЛО сТИРЛИНГА ВТОРОГО РОДА. сОГЛАСНО УПР.
 5,
$$
E=\bigl(\min\max (M-N, 0)p, \ave M(1-{1\over M})^Np,\max(M-1)p\bigr).
$$

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

рАЗУМЕЕТСЯ, ЕСЛИ КЛЮЧИ УЖ ОЧЕНЬ ДЛИННЫЕ, ПОРАЗРЯДНАЯ СОРТИРОВКА НЕ ТАК 
ЭФФЕКТИВНА. пРЕДСТАВЬТЕ СЕБЕ, НАПРИМЕР, ЧТО НУЖНО ОТСОРТИРОВАТЬ ПЕРФОКАРТЫ 
ПО КЛЮЧУ ИЗ 80~КОЛОНОК; КАК ПРАВИЛО, ВСТРЕТИТСЯ ОЧЕНЬ МАЛО ПАР КАРТ, У 
КОТОРЫХ БЫ СОВПАЛИ ПЕРВЫЕ ПЯТЬ КОЛОНОК, ТАК ЧТО ПЕРВЫЕ 75~ПРОСМОТРОВ 
ВЫПОЛНЯТСЯ ПОЧТИ ВПУСТУЮ. пРИ АНАЛИЗЕ ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКИ МЫ 
ОБНАРУЖИЛИ, ЧТО ВОВСЕ НЕ ОБЯЗАТЕЛЬНО ПРОВЕРЯТЬ МНОГО БИТОВ КЛЮЧЕЙ, ЕСЛИ 
ПРОСМАТРИВАТЬ ИХ НЕ СПРАВА НАЛЕВО, А СЛЕВА НАПРАВО. пОЭТОМУ ДАВАЙТЕ 
ВОЗВРАТИМСЯ К ИДЕЕ ПОРАЗРЯДНОЙ СОРТИРОВКИ, В КОТОРОЙ КЛЮЧИ 
ПРОСМАТРИВАЮТСЯ, НАЧИНАЯ СО СТАРШИХ ЦИФР (сц), А НЕ С МЛАДШИХ ЦИФР (мц).

мЫ УЖЕ ОТМЕЧАЛИ, ЧТО сц-ПОРАЗРЯДНАЯ СОРТИРОВКА ЕСТЕСТВЕННЫМ ОБРАЗОМ 
ПРИХОДИТ НА УМ. в САМОМ ДЕЛЕ, НЕТРУДНО ПОНЯТЬ, ПОЧЕМУ ПРИ СОРТИРОВКЕ ПОЧТЫ 
В ОТДЕЛЕНИЯХ СВЯЗИ ПОЛЬЗУЮТСЯ ИМЕННО ЭТИМ МЕТОДОМ. бОЛЬШОЕ КОЛИЧЕСТВО 
ПИСЕМ МОЖНО ОТСОРТИРОВАТЬ ПО ОТДЕЛЬНЫМ МЕШКАМ, СООТВЕТСТВУЮЩИМ 
ГЕОГРАФИЧЕСКИМ ОБЛАСТЯМ; ТЕПЕРЬ КАЖДЫЙ МЕШОК СОДЕРЖИТ УЖЕ МЕНЬШЕЕ 
КОЛИЧЕСТВО ПИСЕМ, КОТОРЫЕ МОЖНО НЕЗАВИСИМО СОРТИРОВАТЬ ПО ДРУГИМ МЕШКАМ, 
СООТВЕТСТВУЮЩИМ ВСЕ МЕНЬШИМ И МЕНЬШИМ ГЕОГРАФИЧЕСКИМ РАЙОНАМ. 
(рАЗУМЕЕТСЯ, ПРЕЖДЕ ЧЕМ ПОДВЕРГАТЬ ПИСЬМА ДАЛЬНЕЙШЕЙ СОРТИРОВКЕ, ИХ 
МОЖНО ПЕРЕПРАВИТЬ ПОБЛИЖЕ К МЕСТУ НАЗНАЧЕНИЯ.) эТОТ ПРИНЦИП "РАЗДЕЛЯЙ И 
ВЛАСТВУЙ" ВЕСЬМА ПРИВЛЕКАТЕЛЕН, И ЕДИНСТВЕННАЯ ПРИЧИНА ЕГО НЕПРИГОДНОСТИ 
ДЛЯ СОРТИРОВКИ ПЕРФОКАРТ В ТОМ, ЧТО БОЛЬШОЕ КОЛИЧЕСТВО СТОПОК ПРИВОДИТ 
К ПУТАНИЦЕ. эТИМ ЖЕ ЯВЛЕНИЕМ ОБоЯСНЯЕТСЯ ОТНОСИТЕЛЬНАЯ ЭФФЕКТИВНОСТЬ 
АЛГОРИТМА~R (ХОТЯ ЗДЕСЬ СНАЧАЛА РАССМАТРИВАЮТСЯ мц), ПОТОМУ ЧТО НАМ 
НИКОГДА НЕ ПРИХОДИТСЯ РАБОТАТЬ БОЛЕЕ ЧЕМ С $M$~СТОПКАМИ И СТОПКИ 
ПРИХОДИТСЯ СЦЕПЛЯТЬ ВСЕГО $p$~РАЗ. с ДРУГОЙ СТОРОНЫ, НЕТРУДНО ПОСТРОИТЬ 
сц-ПОРАЗРЯДНЫЙ МЕТОД С ИСПОЛЬЗОВАНИЕМ СВЯЗАННОГО РАСПРЕДЕЛЕНИЯ ПАМЯТИ С 
ОТРИЦАТЕЛЬНЫМИ СВЯЗЯМИ ДЛЯ ОБОЗНАЧЕНИЕ ГРАНИЦ МЕЖДУ СТОПКАМИ, КАК В 
АЛГОРИТМЕ 5.2.4L. (сМ. УПР. 10.)

пОЖАЛУЙ, НАИЛУЧШИЙ КОМПРОМИССНЫЙ ВЫХОД УКАЗАЛ м.~д.~мАКЛАРЕН [{\sl JACM\/},
 {\bf 13} (1966), 404--411], КОТОРЫЙ ПРЕДЛОЖИЛ ИСПОЛЬЗОВАТЬ 
мц-СОРТИРОВКУ, КАК В АЛГОРИТМЕ~R, \emph{НО ЛИШЬ В ПРИМЕНЕНИИ К СТАРШИМ 
ЦИФРАМ}. эТО НЕ БУДЕТ ПОЛНОЙ СОРТИРОВКОЙ ФАЙЛА, НО В РЕЗУЛЬТАТЕ ФАЙЛ 
СТАНОВИТСЯ ПОЧТИ УПОРЯДОЧЕННЫМ, Т. Е.
%%215
В НЕМ ОСТАЕТСЯ ОЧЕНЬ МАЛО ИНВЕРСИЙ, ТАК ЧТО ДЛЯ ЗАВЕРШЕНИЯ СОРТИРОВКИ 
МОЖНО ВОСПОЛЬЗОВАТЬСЯ МЕТОДОМ ПРОСТЫХ ВСТАВОК. нАШ АНАЛИЗ АЛГОРИТМА 5.2.1м 
ПРИМЕНИМ И К-ЭТОЙ СИТУАЦИИ;
ЕСЛИ КЛЮЧИ РАСПРЕДЕЛЕНЫ РАВНОМЕРНО, ТО ПОСЛЕ СОРТИРОВКИ ФАЙЛА ПО СТАРШИМ 
$p$~ЦИФРАМ В НЕМ ОСТАНЕТСЯ В СРЕДНЕМ
$$
{1\over 4}N(N-1)M^{-p}
$$
ИНВЕРСИЙ. [сМ. ФОРМУЛУ~(5.2.1--14) И УПР.~5.2.1--38.] мАКЛАРЕН ВЫЧИСЛИЛ 
СРЕДНЕЕ ЧИСЛО ОБРАЩЕНИЙ К ПАМЯТИ, ПРИХОДЯЩЕЕСЯ НА ОДИН ОБРАБАТЫВАЕМЫЙ 
ЭЛЕМЕНТ, И ОКАЗАЛОСЬ, ЧТО ОПТИМАЛЬНЫЙ ВЫБОР ЗНАЧЕНИЙ~$M$ И~$p$ (В 
ПРЕДПОЛОЖЕНИИ, ЧТО $M$---СТЕПЕНЬ ДВОЙКИ, КЛЮЧИ РАВНОМЕРНО РАСПРЕДЕЛЕНЫ 
И~$N/M^p\le 0.1$, ТАК.ЧТО ОТКЛОНЕНИЯ ОТ РАВНОМЕРНОГО РАСПРЕДЕЛЕНИЯ 
ПРИЕМЛЕМЫ) ОПИСЫВАЕТСЯ СЛЕДУЮЩЕЙ ТАБЛИЦЕЙ:
\ctable{
\hfill$#$\bskip&&\bskip\hfill$#$\bskip\cr
N= & 100 & 1000 & 5000 & 10000 & 50000 & 100000\cr
\hbox{нАИЛУЧШЕЕ } M=& 32 &  128 &  256 &  512 &  1024 &   1024\cr
\hbox{нАИЛУЧШЕЕ } p=& 2 & 2 & 2 & 2 & 2  & 2\cr
      \bar \beta(N)=& 19.3 & 18.5 & 18.2 &  18.2 &  18.1 &   18.0 \cr
}
зДЕСЬ $\bar\beta(N)$---СРЕДНЕЕ ЧИСЛО ОБРАЩЕНИЙ К ПАМЯТИ НА ОДИН 
СОРТИРУЕМЫЙ ЭЛЕМЕНТ; ЭТА ВЕЛИЧИНА ОГРАНИЧЕНА ПРИ $N\to\infty$, 
ЕСЛИ ВЗЯТЬ $p=2$ И~$M>\sqrt N$, ТАК ЧТО СРЕДНЕЕ ВРЕМЯ СОРТИРОВКИ 
ЕСТЬ $O(N)$, А НЕ $O(N \log N)$. эТОТ МЕТОД ЯВЛЯЕТСЯ 
УСОВЕРШЕНСТВОВАНИЕМ МЕТОДА ВСТАВОК В НЕСКОЛЬКО СПИСКОВ (АЛГОРИТМ~5.2.1м), 
КОТОРЫЙ, ПО СУЩЕСТВУ, ПРЕДСТАВЛЯЕТ СОБОЙ СЛУЧАЙ $p=1$. в УПР.~12 
ПРИВОДИТСЯ ИНТЕРЕСНАЯ ПРОЦЕДУРА мАКЛАРЕНА ДЛЯ 
ОКОНЧАТЕЛЬНОГО ПЕРЕРАЗМЕЩЕНИЯ ПОСЛЕ ЧАСТИЧНОЙ СОРТИРОВКИ ФАЙЛА С 
ИСПОЛЬЗОВАНИЕМ СПИСКОВ.

еСЛИ ВОСПОЛЬЗОВАТЬСЯ МЕТОДАМИ АЛГОРИТМА~5.2D И УПР.~5.2-13, ТО МОЖНО 
ОБОЙТИСЬ БЕЗ ПОЛЕЙ СВЯЗИ; ПРИ ЭТОМ В ДОПОЛНЕНИЕ К ПАМЯТИ, ЗАНЯТОЙ САМИМИ 
ЗАПИСЯМИ, ПОТРЕБУЕТСЯ ВСЕГО $O(\sqrt N)$~ЯЧЕЕК. еСЛИ ИСХОДНЫЕ ДАННЫЕ 
РАСПРЕДЕЛЕНЫ РАВНОМЕРНО, ТО СРЕДНЕЕ ВРЕМЯ СОРТИРОВКИ ПРОПОРЦИОНАЛЬНО~$N$.

\excercises
\rex[20] аЛГОРИТМ ИЗ УПР.~5.2--13 ПОКАЗЫВАЕТ, КАК МОЖНО ВЫПОЛНИТЬ 
РАСПРЕДЕЛЯЮЩУЮ СОРТИРОВКУ, ИМЕЯ ПРОСТРАНСТВО ПАМЯТИ ВСЕГО ПОД 
$N$~ЗАПИСЕЙ (И $M$~ПОЛЕЙ СЧЕТЧИКОВ), А НЕ ПОД $2N$~ЗАПИСЕЙ. пРИВОДИТ ЛИ 
ЭТА ИДЕЯ К УСОВЕРШЕНСТВОВАНИЮ АЛГОРИТМА ПОРАЗРЯДНОЙ СОРТИРОВКИ, 
ПРОИЛЛЮСТРИРОВАННОГО В ТАБЛ.~1?

\ex[13] яВЛЯЕТСЯ ЛИ АЛГОРИТМ~R АЛГОРИТМОМ "УСТОЙЧИВОЙ" СОРТИРОВКИ?
%%216

\ex[15] оБоЯСНИТЕ, ПОЧЕМУ В АЛГОРИТМЕ~H ПЕРЕМЕННОЙ $|BOTM|[0]$ 
ПРИСВАИВАЕТСЯ ЗНАЧЕНИЕ УКАЗАТЕЛЯ НА ПЕРВУЮ ЗАПИСЬ В "ОБоЕДИНЕННОЙ" 
ОЧЕРЕДИ, 
\emph{НЕСМОТРЯ НА ТО ЧТО СТОПКА 0 МОГЛА БЫТЬ ПУСТОЙ.}

\rex[23] вО ВРЕМЯ РАБОТЫ АЛГОРИТМА~R ВСЕ $M$~СТОПОК ХРАНЯТСЯ В 
ВИДЕ СВЯЗАННЫХ ОЧЕРЕДЕЙ (ПЕРВЫМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ). 
иССЛЕДУЙТЕ ИДЕЮ СВЯЗЫВАНИЯ ЭЛЕМЕНТОВ СТОПОК КАК В \emph{СТЕКЕ}. (нА 
РИС.~33 СТРЕЛКИ ПОЙДУТ НЕ ВВЕРХ, А ВНИЗ, И ТАБЛИЦА~|BOTM| СТАНЕТ НЕ 
НУЖНА.) пОКАЖИТЕ, ЧТО ЕСЛИ СЦЕПЛЯТЬ СТОПКИ В СООТВЕТСТВУЮЩЕМ ПОРЯДКЕ, ТО 
МОЖЕТ ПОЛУЧИТЬСЯ ПРАВИЛЬНЫЙ МЕТОД СОРТИРОВКИ. бУДЕТ ЛИ ЭТОТ АЛГОРИТМ 
БОЛЕЕ ПРОСТЫМ ИЛИ БОЛЕЕ БЫСТРЫМ?

\ex[M24] пУСТЬ $g_{MN}(z)=\sum p_{MNk}z^k$, ГДЕ $p_{MNk}$--- ВЕРОЯТНОСТЬ 
ТОГО, ЧТО ПОСЛЕ СЛУЧАЙНОГО ПРОСМОТРА ПОРАЗРЯДНОЙ СОРТИРОВКИ, РАЗЛОЖИВШЕГО 
$N$~ЭЛЕМЕНТОВ НА $M$~СТОПОК, ПОЛУЧИЛОСЬ РОВНО $k$~ПУСТЫХ СТОПОК. (a) 
пОКАЖИТЕ, ЧТО
$g_{M,N+1}(z)=g_{MN}(z)+((1-z)/M)g'_{MN}(z)$. (b) нАЙДИТЕ ПРИ ПОМОЩИ 
УКАЗАННОГО СООТНОШЕНИЯ ПРОСТЫЕ ВЫРАЖЕНИЯ ДЛЯ МАТЕМАТИЧЕСКОГО ОЖИДАНИЯ И 
ДИСПЕРСИИ ЭТОГО РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ КАК ФУНКЦИЙ ОТ~$M$ И~$N$.

\ex[20] кАКИЕ ИЗМЕНЕНИЯ НЕОБХОДИМО ВНЕСТИ В ПРОГРАММУ~R, ЧТОБЫ 
ОНА СОРТИРОВАЛА НЕ ТРЕХБАЙТОВЫЕ КЛЮЧИ, А ВОСЬМИБАЙТОВЫЕ? сЧИТАЕТСЯ, ЧТО 
СТАРШИЕ БАЙТЫ КЛЮЧА~$K_i$ ХРАНЯТСЯ В ЯЧЕЙКЕ $|KEY|+i(1:5)$, А ТРИ 
МЛАДШИХ БАЙТА, КАК И РАНЬШЕ,---В ЯЧЕЙКЕ $|INPUT|+i(1:3)$. кАКОВО ВРЕМЯ 
РАБОТЫ ПРОГРАММЫ С ЭТИМИ ИЗМЕНЕНИЯМИ?

\ex[20] оБСУДИТЕ, В ЧЕМ СОСТОИТ СХОДСТВО И ОТЛИЧИЕ АЛГОРИТМА~R И 
АЛГОРИТМА ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКИ (АЛГОРИТМ~5.2.2R).

\rex[20] в АЛГОРИТМАХ ПОРАЗРЯДНОЙ СОРТИРОВКИ, ОБСУЖДАВШИХСЯ В ТЕКСТЕ,
 ПРЕДПОЛАГАЛОСЬ, ЧТО ВСЕ СОРТИРУЕМЫЕ КЛЮЧИ НЕОТРИЦАТЕЛЬНЫ. кАКИЕ 
ИЗМЕНЕНИЯ СЛЕДУЕТ ВНЕСТИ В ЭТИ АЛГОРИТМЫ В ТОМ СЛУЧАЕ, КОГДА КЛЮЧАМИ 
МОГУТ БЫТЬ И ОТРИЦАТЕЛЬНЫЕ ЧИСЛА, ПРЕДСТАВЛЕННЫЕ В \emph{ДОПОЛНИТЕЛЬНОМ 
ИЛИ ОБРАТНОМ} КОДЕ?

\ex[20] (пРОДОЛЖЕНИЕ УПР.~8.) кАКИЕ ИЗМЕНЕНИЯ НУЖНО ВНЕСТИ В ЭТИ 
АЛГОРИТМЫ В СЛУЧАЕ, КОГДА КЛЮЧАМИ ЯВЛЯЮТСЯ ЧИСЛА, ПРЕДСТАВЛЕННЫЕ В 
ВИДЕ АБСОЛЮТНОЙ ВЕЛИЧИНЫ СО ЗНАКОМ?

\ex[30] сКОНСТРУИРУЙТЕ АЛГОРИТМ ПОРАЗРЯДНОЙ СОРТИРОВКИ 
"СНАЧАЛА-ПО-СТАРШЕЙ-ЦИФРЕ", ИСПОЛЬЗУЮЩИЙ СВЯЗАННЕЕ РАСПРЕДЕЛЕНИЕ. (тАК КАК 
РАЗМЕР ПОДФАЙЛОВ ВСЕ УМЕНЬШАЕТСЯ, ТО РАЗУМНО УМЕНЬШИТЬ $M$, А ДЛЯ 
СОРТИРОВКИ КОРОТКИХ ФАЙЛОВ ПРИМЕНИТЬ НЕ ПОРАЗРЯДНУЮ СОРТИРОВКУ.)

\ex[16] пЕРЕСТАНОВКА ШЕСТНАДЦАТИ ИСХОДНЫХ ЧИСЕЛ, ПОКАЗАННАЯ В ТАБЛ.~1,
 СОДЕРЖИТ ВНАЧАЛЕ 41 ИНВЕРСИЮ. пОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ ИНВЕРСИЙ, 
РАЗУМЕЕТСЯ, НЕТ СОВСЕМ. сКОЛЬКО ИНВЕРСИЙ ОСТАЛОСЬ БЫ В ФАЙЛЕ, ЕСЛИ БЫ 
МЫ ПРОПУСТИЛИ ПЕРВЫЙ ПРОСМОТР, А ВЫПОЛНИЛИ БЫ ПОРАЗРЯДНУЮ СОРТИРОВКУ 
ЛИШЬ ПО ЦИФРАМ ДЕСЯТКОВ И СОТЕН? сКОЛЬКО ИНВЕРСИЙ ОСТАНЕТСЯ, ЕСЛИ 
ПРОПУСТИТЬ КАК ПЕРВЫЙ, ТАК И ВТОРОЙ ПРОСМОТРЫ?

\ex[24] (м. д. мАКЛАРЕН.) пРЕДПОЛОЖИМ, АЛГОРИТМ~R ПРИМЕНИЛИ ТОЛЬКО К 
$p$~СТАРШИМ ЦИФРАМ РЕАЛЬНЫХ КЛЮЧЕЙ; ТОГДА ФАЙЛ, ЕСЛИ ЧИТАТЬ ЕГО ПО 
ПОРЯДКУ, УКАЗАННОМУ СВЯЗЯМИ, ПОЧТИ ОТСОРТИРОВАН, НО КЛЮЧИ, У КОТОРЫХ 
СТАРШИЕ $p$~ЦИФР СОВПАДАЮТ, МОГУТ БЫТЬ НЕУПОРЯДОЧЕНЫ. пРИДУМАЙТЕ 
АЛГОРИТМ ПЕРЕРАЗМЕЩЕНИЯ ЗАПИСЕЙ НА ТОМ ЖЕ МЕСТЕ ТАК, ЧТОБЫ КЛЮЧИ 
РАСПОЛОЖИЛИСЬ ПО ПОРЯДКУ: $K_1\le K_2\le\ldots\le K_N$. [\emph{уКАЗАНИЕ:} 
ЧАСТНЫЙ СЛУЧАЙ, КОГДА ФАЙЛ ПОЛНОСТЬЮ ОТСОРТИРОВАН, МОЖНО НАЙТИ В ОТВЕТЕ К 
УПР. 5.2--12, ЕГО МОЖНО СКОМБИНИРОВАТЬ С ПРОСТЫМИ ВСТАВКАМИ БЕЗ ПОТЕРИ 
ЭФФЕКТИВНОСТИ, ТАК КАК В ФАЙЛЕ ОСТАЛОСЬ МАЛО ИНВЕРСИЙ.]

\ex[40] рЕАЛИЗУЙТЕ МЕТОД ВНУТРЕННЕЙ СОРТИРОВКИ, ПРЕДЛОЖЕННЫЙ В ТЕКСТЕ В 
КОНЦЕ ЭТОГО ПУНКТА, ПОЛУЧИВ ПРОГРАММУ СОРТИРОВКИ СЛУЧАЙНЫХ ДАННЫХ ЗА 
$O(N)$~ЕДИНИЦ ВРЕМЕНИ, ТРЕБУЮЩУЮ ВСЕГО $O(N)$ ДОПОЛНИТЕЛЬНЫХ ЯЧЕЕК ПАМЯТИ.

\ex[22] пОСЛЕДОВАТЕЛЬНОСТЬ ИГРАЛЬНЫХ КАРТ
%%217
МОЖНО ОТСОРТИРОВАТЬ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ: |т| |2| \dots |в| |д| |к| ОТ 
ВЕРХНЕЙ КАРТЫ К НИЖНЕЙ, ЗА ДВА ПРОСМОТРА, РАСКЛАДЫВАЯ КАРТЫ КАЖДЫЙ РАЗ 
ЛИШЬ В ДВЕ СТОПКИ: РАЗЛОЖИТЕ КАРТЫ ЛИЦЕВОЙ СТОРОНОЙ ВНИЗ В ДВЕ СТОПКИ, 
СОДЕРЖАЩИЕ СООТВЕТСТВЕННО |т| |2| |9| |3| |10| И |4| |в| |5| |6| |д| |к| 
|7| |8| (ОТ НИЖНЕЙ КАРТЫ К ВЕРХНЕЙ); ЗАТЕМ ПОЛОЖИТЕ ВТОРУЮ СТОПКУ ПОВЕРХ 
ПЕРВОЙ, ПОВЕРНИТЕ КОЛОДУ ЛИЦЕВОЙ СТОРОНОЙ ВВЕРХ И РАЗЛОЖИТЕ В ДВЕ СТОПКИ 
|т| |2| |3| |4| |5| |6| |7| |8| И |9| |10| |в| |д| |к|.  сОЕДИНИТЕ ЭТИ ДВЕ 
СТОПКИ И ПОВЕРНИТЕ ИХ ЛИЦЕВОЙ СТОРОНОЙ ВВЕРХ. кОЛОДА ОТСОРТИРОВАНА.

дОКАЖИТЕ, ЧТО ПРИВЕДЕННУЮ ВЫШЕ ПОСЛЕДОВАТЕЛЬНОСТЬ КАРТ НЕЛЬЗЯ 
ОТСОРТИРОВАТЬ В \emph{УБЫВАЮЩЕМ} ПОРЯДКЕ: |к| |д| |в| \dots |2| |т|, ОТ 
ВЕРХНЕЙ КАРТЫ К НИЖНЕЙ, ЗА ДВА ПРОСМОТРА, ДАЖЕ ЕСЛИ РАЗРЕШЕНО РАСКЛАДЫВАТЬ 
КАРТЫ В ТРИ СТОПКИ. (сДАВАТЬ КАРТЫ, НУЖНО ВСЕГДА СВЕРХУ КОЛОДЫ, 
ПОВОРАЧИВАЯ ИХ ПРИ РАЗДАЧЕ РУБАШКОЙ ВВЕРХ. нА РИСУНКЕ ВЕРХНЯЯ КАРТА КОЛОДЫ 
ИЗОБРАЖЕНА СПРАВА, А НИЖНЯЯ---СЛЕВА.)

\ex[м25] рАССМОТРИТЕ ЗАДАЧУ ИЗ УПР.~14 В СЛУЧАЕ, КОГДА КАРТЫ 
РАЗДАЮТСЯ ЛИЦЕВОЙ СТОРОНОЙ ВВЕРХ, А НЕ ВНИЗ. тАКИМ ОБРАЗОМ, ОДИН ПРОСМОТР 
МОЖНО ПОТРАТИТЬ НА ПРЕОБРАЗОВАНИЕ ВОЗРАСТАЮЩЕГО ПОРЯДКА В УБЫВАЮЩИЙ. 
сКОЛЬКО НУЖНО ПРОСМОТРОВ?

\bigskip\epigraph
кАК ТОЛЬКО ПОЯВИТСЯ АНАЛИТИЧЕСКАЯ МАШИНА, ОНА, БЕЗУСЛОВНО, ОПРЕДЕЛИТ 
ДАЛЬНЕЙШИЙ ПУТЬ РАЗВИТИЯ НАУКИ. вСЯКИЙ РАЗ, КОГДА С ЕЕ ПОМОЩЬЮ БУДЕТ 
НАЙДЕН КАКОЙ-ЛИБО РЕЗУЛЬТАТ, ТУТ ЖЕ ВОЗНИКНЕТ ВОПРОС: НЕЛЬЗЯ ЛИ ТОТ ЖЕ 
РЕЗУЛЬТАТ ПОЛУЧИТЬ НА ЭТОЙ МАШИНЕ ЗА КРАТЧАЙШЕЕ ВРЕМЯ?
\signed чАРЛЬЗ бЭББИДЖ (1864)

%%218
\bye