\input style
%% 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


\bye