\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