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

%%438
\htable{тАБЛИЦА 1}%
{хАРАКТЕРИСТИКИ ОПТИМАЛЬНОГО ДЕРЕВА $A_m(n)$, $k_m(n)$ ПРИ $\alpha=\beta=1$}%
{$n=#$\hfill&
\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&
\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&\hfill$\,#\,$&
\hfill$\,#\,$\hfill&$n=#$\hfill\cr
\omit
  & m=1 &  m=2 & m=3 & m=4 & m=5 & m=6 & m=7 & m=8 & m=9 & m=10& m=11& m=12& \hbox{оПИСАНИЕ ДЕРЕВА}\cr
1 &  0,0&      &     &     &     &     &     &     &     &     &     &     &-         & 1\cr
2 &  6,2&  0,1 &     &     &     &     &     &     &     &     &     &     &1:1       & 2\cr
3 & 12,3&  6,1 &  0,1&     &     &     &     &     &     &     &     &     &1:1:1     & 3\cr
4 & 20,4& 12,1 &  6,1&  0,1&     &     &     &     &     &     &     &     &1:1:1:1   & 4\cr
5 & 30,5& 18,2 & 12,1&  6,1&  0,1&     &     &     &     &     &     &     &1:1:1:1:1 & 5\cr
6 & 42,2& 24,3 & 18,1& 12,1&  6,1&  0,1&     &     &     &     &     &     & 3:3      & 6\cr
7 & 52,3& 32,3 & 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     &     &     & 1:3:3    & 7\cr
8 & 62,3& 40,4 & 30,2& 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     &     & 2:3:3    & 8\cr
9 & 72,3& 50,4 & 36,3& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     &     &     & 3:3:3    & 9\cr
10& 84,3& 60,5 & 44,3& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     &     & 3:3:4    &10\cr
11& 96,3& 72,4 & 52,3& 42,2& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1&     & 3:4:4    &11\cr
12&108,3& 82,4 & 60,4& 48,3& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1&  0,1& 4:4:4    &12\cr
13&121,4& 92,4 & 70,4& 56,3& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1&  6,1& 3:3:3:4  &13\cr
14&134,4&102,5 & 80,4& 64,3& 54,2& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 12,1& 3:3:4:4  &14\cr
15&147,4&114,5 & 90,5& 72,3& 60,3& 54,1& 48,1& 42,1& 36,1& 30,1& 24,1& 18,1& 3:4:4:4  &15\cr
16&160,4&124,7 &102,4& 80,4& 68,3& 60,1& 54,1& 48,1& 42,1& 36,1& 30,1& 24,1& 4:4:4:4  &16\cr
17&175,4&134,8 &112,4& 90,4& 76,3& 66,2& 60,1& 54,1& 48,1& 42,1& 36,1& 30,1& 4:4:4:5  &17\cr
18&190,4&144,9 &122,4&100,4& 84,3& 72,3& 66,1& 60,1& 54,1& 48,1& 42,1& 36,1& 4:4:5:5  &18\cr
19&205,4&156,9 &132,5&110,4& 92,3& 80,3& 72,1& 66,1& 60,1& 54,1& 48,1& 42,1& 4:5:5:5  &19\cr
20&220,4&168,9 &144,4&120,5&100,4& 88,3& 78,2& 72,1& 66,1& 60,1& 54,1& 48,1& 5:5:5:5  &20\cr
21&236,5&180,9 &154,4&132,4&110,4& 96,3& 84,3& 78,1& 72,1& 66,1& 60,1& 54,1& 4:4:4:4:5&21\cr
22&252,3&192,10&164,4&142,4&120,4&104,3& 92,3& 84,1& 78,1& 72,1& 66,1& 60,1& 4:9:9    &22\cr
23&266,3&204,11&174,5&152,4&130,4&112,3&100,3& 90,2& 84,1& 78,1& 72,1& 66,1& 5:9:9    &23\cr
24&282,3&216,12&186,5&162,5&140,4&120,4&108,3& 96,3& 90,1& 84,1& 78,1& 72,1& 5:9:10   &24\cr
25&296,3&229,12&196,7&174,4&150,5&130,4&116,3&104,3& 96,1& 90,1& 84,1& 78,1& 7:9:9    &25\cr
}
нАШ ВЫВОД ВЫРАЖЕНИЯ~$(2)$ ПОКАЗЫВАЕТ, ЧТО ВСЕГДА, КОГДА ИСПОЛЬЗУЮТСЯ 
$P+1$~РАВНЫХ БУФЕРОВ, БУДЕТ ИМЕТЬ МЕСТО СООТНОШЕНИЕ~$\alpha\le\beta$. 
пРЕДЕЛЬНЫЙ СЛУЧАЙ~$\alpha=\beta$, ПОКАЗАННЫЙ В ТАБЛ.~1 И НА РИС.~93, 
ВОЗНИКАЕТ ТОГДА, КОГДА ТРЕБУЕТСЯ МИНИМИЗИРОВАТЬ САМО ВРЕМЯ ПОИСКА 
БЕЗОТНОСИТЕЛЬНО КО ВРЕМЕНИ ПЕРЕДАЧИ.

вЕРНЕМСЯ К НАШЕЙ ПЕРВОНАЧАЛЬНОЙ ЗАДАЧЕ. мЫ ЕЩЕ НЕ РАССМОТРЕЛИ, КАК 
ПОЛУЧИТЬ НАЧАЛЬНЫЕ ОТРЕЗКИ; БЕЗ СОВМЕЩЕНИЯ ЧТЕНИЯ/ЗАПИСИ/ВЫЧИСЛЕНИЙ 
ВЫБОР С ЗАМЕЩЕНИЕМ ТЕРЯЕТ НЕКОТОРЫЕ ИЗ СВОИХ ПРЕИМУЩЕСТВ. вОЗМОЖНО, НАМ 
СЛЕДУЕТ ЗАПОЛНИТЬ ВСЮ ВНУТРЕННЮЮ
\picture{рИС. 93. оПТИМАЛЬНЫЙ СПОСОБ СЛИЯНИЯ 22 НАЧАЛЬНЫХ ОТРЕЗКОВ РАВНОЙ 
ДЛИНЫ, ЕСЛИ В ТЕОРЕМЕ н $\alpha=\beta$. эТА СХЕМА МИНИМИЗИРУЕТ ВРЕМЯ 
ПОИСКА ПРИ ПРЕДПОЛОЖЕНИЯХ, ПРИВЕДШИХ К ФОРМУЛЕ (2).
}
ПАМЯТЬ, ОТСОРТИРОВАТЬ ЕЕ И ВЫВЕСТИ РЕЗУЛЬТАТ; КАЖДУЮ ИЗ ТАКИХ ОПЕРАЦИЙ 
ВВОДА И ВЫВОДА МОЖНО ВЫПОЛНИТЬ С ОДНИМ ПОИСКОМ. иЛИ, ВОЗМОЖНО, ЛУЧШЕ 
ИСПОЛЬЗОВАТЬ, СКАЖЕМ, 20\% ПАМЯТИ КАК КОМБИНИРОВАННЫЙ БУФЕР ВВОДА/ВЫВОДА 
И ВЫПОЛНЯТЬ ВЫБОР С ЗАМЕЩЕНИЕМ. эТО ТРЕБУЕТ В ПЯТЬ РАЗ БОЛЬШЕ ПОИСКОВ 
(ДОПОЛНИТЕЛЬНО ПРИМЕРНО 60~С!), НО УМЕНЬШАЕТ ЧИСЛО НАЧАЛЬНЫХ ОТРЕЗКОВ 
СО~100 ДО~64; УМЕНЬШЕНИЕ БУДЕТ ЕЩЕ БОЛЕЕ РЕЗКИМ, ЕСЛИ ВВОДНЫЙ ФАЙЛ УЖЕ 
ПОЧТИ УПОРЯДОЧЕН.

еСЛИ МЫ РЕШИЛИ НЕ ИСПОЛЬЗОВАТЬ ВЫБОР С ЗАМЕЩЕНИЕМ, ТО ОПТИМАЛЬНОЕ ДЕРЕВО 
ДЛЯ $S=100$, $\alpha=0.00145$, $\beta=0.01545$ 
[СМ. (2)] ОКАЗЫВАЕТСЯ ВЕСЬМА ПРОЗАИЧЕСКИМ. эТО ПРОСТО 10-ПУТЕВОЕ СЛИЯНИЕ, 
ВЫПОЛНЯЕМОЕ ЗА ДВА ПРОХОДА ПО ДАННЫМ. вЫДЕЛЯЯ 30~С НА ВНУТРЕННЮЮ 
СОРТИРОВКУ (СКАЖЕМ, 100~БЫСТРЫХ СОРТИРОВОК), ПОЛУЧАЕМ, ЧТО НАЧАЛЬНЫЙ 
РАСПРЕДЕЛИТЕЛЬНЫЙ ПРОХОД, ЗАНИМАЕТ ПРИМЕРНО
$2{1\over2}$~МИН, А КАЖДЫЙ ПРОХОД СЛИЯНИЯ ЗАНИМАЕТ ПОЧТИ 5~МИН; В ИТОГЕ
ИМЕЕМ $12.4$~МИН. еСЛИ МЫ РЕШИЛИ ИСПОЛЬЗОВАТЬ ВЫБОР С ЗАМЕЩЕНИЕМ, ТО 
ОПТИМАЛЬНОЕ ДЕРЕВО ДЛЯ $S=64$ ОКАЗЫВАЕТСЯ ОДИНАКОВО НЕИНТЕРЕСНЫМ (ДВА 
ПРОХОДА 8-ПУТЕВОГО СЛИЯНИЯ); НАЧАЛЬНЫЙ РАСПРЕДЕЛИТЕЛЬНЫЙ ПРОХОД ЗАНИМАЕТ 
ПРИМЕРНО $3{1\over2}$~МИН, КАЖДЫЙ ПРОХОД СЛИЯНИЯ---ОКОЛО $4{1\over2}$~МИН, 
ОЦЕНКА ОБЩЕГО ВРЕМЕНИ СОСТАВЛЯЕТ 12.6~МИН.
%%440
вСПОМНИМ, ЧТО В ОБОИХ ЭТИХ МЕТОДАХ ФАКТИЧЕСКИ ПОЛНОСТЬЮ 
ИСКЛЮЧАЕТСЯ СОВМЕЩЕНИЕ ЧТЕНИЯ/ЗАПИСИ/ВЫЧИСЛЕНИЙ, ЧТОБЫ ИМЕТЬ БОЛЬШИЕ 
БУФЕРЫ (С ЦЕЛЬЮ УМЕНЬШЕНИЯ ВРЕМЕНИ ПОИСКА). нИ ОДНА ИЗ ЭТИХ ОЦЕНОК НЕ 
ВКЛЮЧАЕТ ВРЕМЯ, КОТОРОЕ МОЖЕТ ПОТРЕБОВАТЬСЯ ДЛЯ ОПЕРАЦИЙ КОНТРОЛЬНОГО ЧТЕНИЯ.

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

\section *дРУГОЙ СПОСОБ РАСПРЕДЕЛЕНИЯ БУФЕРОВ. дАВИД~э.~фЕРГЮСОН УКАЗАЛ 
[{\sl CACM,\/} {\bf 14} (1971), 476--478], ЧТО МОЖНО УМЕНЬШИТЬ 
ВРЕМЯ ПОИСКА, ЕСЛИ НЕ ДЕЛАТЬ ВСЕ БУФЕРЫ ОДНОГО РАЗМЕРА. тА ЖЕ МЫСЛЬ И 
ПРИМЕРНО В ТО ЖЕ ВРЕМЯ ПРИШЛА В ГОЛОВУ ЕЩЕ НЕСКОЛЬКИМ ЛИЦАМ 
[S.~J.~Waters, {\sl Comp.~J.,\/} {\bf 14} (1971), 109--112; 
Ewing~S.~Walker, Software Age, {\bf 4} (August-September, 1970), 16--17].

пРЕДПОЛОЖИМ, ЧТО МЫ ВЫПОЛНЯЕМ ЧЕТЫРЕХПУТЕВОЕ СЛИЯНИЕ ОТРЕЗКОВ РАВНОЙ 
ДЛИНЫ~$L_0$, ИМЕЯ ПАМЯТЬ В $M$~ЛИТЕР. еСЛИ МЫ РАЗДЕЛИМ ПАМЯТЬ НА РАВНЫЕ 
БУФЕРЫ РАЗМЕРА~$B=M/5$, ТО НАМ ПОТРЕБУЕТСЯ ОКОЛО $L_0/B$~ПОИСКОВ ДЛЯ 
КАЖДОГО ВВОДНОГО ФАЙЛА И $4L_0/B$~ПОИСКОВ ДЛЯ ВЫВОДА, ЧТО В СУММЕ ДАЕТ 
$8L_0/B = 40L_0/M$~ПОИСКОВ. нО ЕСЛИ МЫ ИСПОЛЬЗУЕМ ЧЕТЫРЕ БУФЕРА ВВОДА 
РАЗМЕРА~$M/6$ И ОДИН БУФЕР ВЫВОДА РАЗМЕРА~$M/3$, ТО НАМ ПОТРЕБУЕТСЯ 
ВСЕГО ЛИШЬ ОКОЛО $4\times(6L_0/M)+4\times(3L_0/M)=36L_0/M$~ПОИСКОВ! 
вРЕМЕНА ПЕРЕДАЧИ В ОБОИХ СЛУЧАЯХ ОДИНАКОВЫ, ТАК ЧТО МЫ НИЧЕГО НЕ 
ПОТЕРЯЕМ ОТ ЭТОГО ИЗМЕНЕНИЯ.

в ОБЩЕМ СЛУЧАЕ ПРЕДПОЛОЖИМ, ЧТО МЫ ХОТИМ СЛИТЬ ОТСОРТИРОВАННЫЕ ФАЙЛЫ, 
ИМЕЮЩИЕ ДЛИНЫ~$L_0$,~\dots, $L_p$, В ОТСОРТИРОВАННЫЙ ФАЙЛ 
ДЛИНЫ~$L_{P+1}=L_1+\cdots+L_P$, И ПРЕДПОЛОЖИМ, ЧТО ДЛЯ $k\hbox{-ГО}$ФАЙЛА 
ИСПОЛЬЗУЕТСЯ БУФЕР РАЗМЕРА~$B_k$. тОГДА
$$
B_1+\cdots+B_P+B_{P+1}=M,
\eqno(6)
$$
ГДЕ $M$---ОБЩИЙ ОБRЕМ НАЛИЧНОЙ ВНУТРЕННЕЙ ПАМЯТИ. чИСЛО ПОИСКОВ БУДЕТ 
ПРИБЛИЗИТЕЛЬНО РАВНО
$$
{L_1\over B_1}+\cdots+{L_P\over B_P}+{L_{P+1}\over B_{P+1}}.
\eqno(7)
$$
пОПЫТАЕМСЯ МИНИМИЗИРОВАТЬ ЭТУ ВЕЛИЧИНУ ПРИ УСЛОВИИ~(6), СЧИТАЯ ДЛЯ 
УДОБСТВА, ЧТО $B_k$ НЕ ОБЯЗАНЫ БЫТЬ ЦЕЛЫМИ. еСЛИ УВЕЛИЧИТЬ~$B_j$ 
НА~$\delta$ И УМЕНЬШИТЬ~$B_k$ НА ТУ ЖЕ НЕБОЛЬШУЮ ВЕЛИЧИНУ, ТО ЧИСЛО 
ПОИСКОВ ИЗМЕНИТСЯ НА
$$
{L_j\over B_j+\delta}-{L_j\over B_j}+{L_k\over B_k-\delta}-{L_k\over B_k} 
=\left({L_k\over B_k(B_k-\delta)}-{L_j\over B_j(B_j+\delta)}\right)\delta,
$$
Т.~Е., РАСПРЕДЕЛЕНИЕ МОЖНО УЛУЧШИТЬ, ЕСЛИ $L_j/B^2_j\ne L_k/B^2_k$. 
сЛЕДОВАТЕЛЬНО,
%% 441
МЫ ПОЛУЧИМ МИНИМАЛЬНОЕ ЧИСЛО ПОИСКОВ, ТОЛЬКО ЕСЛИ
$$
{L_1\over B^2_1}=\cdots={L_P\over B^2_P}={L_{P+1}\over B^2_{P+1}}.
\eqno(8)
$$
тАК КАК МИНИМУМ ОБЯЗАТЕЛЬНО СУЩЕСТВУЕТ, ОН ДОЛЖЕН ДОСТИГАТЬСЯ ПРИ
$$
B_k=\sqrt{L_k}M/(\sqrt{L_1}+\cdots+\sqrt{L_{P+1}}),\quad 1\le k\le P+1,
\eqno(9)
$$
ПОСКОЛЬКУ ЭТО ЕДИНСТВЕННЫЕ ЗНАЧЕНИЯ~$B_1$,~\dots, $B_{P+1}$, 
УДОВЛЕТВОРЯЮЩИЕ ОДНОВРЕМЕННО~(6) И~(8). пОДСТАНОВКА ЭТИХ ЗНАЧЕНИЙ 
В~(7) ДАЕТ ВЕСЬМА ПРОСТУЮ ФОРМУЛУ ДЛЯ ОБЩЕГО ЧИСЛА ПОИСКОВ:
$$
(\sqrt{L_1}+\cdots+\sqrt{L_{P+1}})^2/M,
\eqno(10)
$$
КОТОРУЮ МОЖНО СРАВНИТЬ С ЧИСЛОМ $(P+1)(L_1+\cdots+L_{P+1})/M$,
 ПОЛУЧАЮЩИМСЯ В ТОМ СЛУЧАЕ, ЕСЛИ ВСЕ БУФЕРЫ РАВНЫ ПО ДЛИНЕ.
вЫИГРЫШ РАВЕН~$\sum_{1\le j<k\le P+1}(\sqrt{L_j}-\sqrt{L_k})^2/M$   
СОГЛАСНО УПР.~1.2.3-31. к СОЖАЛЕНИЮ, ФОРМУЛА (10) НЕ ГОДИТСЯ ДЛЯ ПРОСТОГО 
ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОЙ СХЕМЫ СЛИЯНИЯ, КАК В ТЕОРЕМЕ~K (СР.~С УПР.~14).

\section дОПОЛНИТЕЛЬНЫЕ СООБРАЖЕНИЯ. еСЛИ ИСПОЛЬЗУЮТСЯ ДВА 
ДИСКОВЫХ УСТРОЙСТВА (ОДНО ДЛЯ ЧТЕНИЯ И ОДНО ДЛЯ ЗАПИСИ), ТО МОЖНО 
СОВМЕСТИТЬ ЧАСТЬ ВРЕМЕНИ ЗАПИСИ ЦЕНОЙ ДОПОЛНИТЕЛЬНОГО БУФЕРА ВЫВОДА. 
еСЛИ ИСПОЛЬЗУЕТСЯ МЕТОД "ПРОГНОЗИРОВАНИЯ" (Т.~Е.~МЫ СМОТРИМ НА ПОСЛЕДНИЙ 
КЛЮЧ В КАЖДОМ БУФЕРЕ ВВОДА, ЧТОБЫ ОПРЕДЕЛИТЬ, КАКОЙ БУФЕР ПЕРВЫМ 
ОСВОБОДИТСЯ), ТО МОЖНО СОВМЕСТИТЬ ЧАСТЬ ВРЕМЕНИ ЧТЕНИЯ. к СОЖАЛЕНИЮ, 
ПРОСТАЯ ПРОЦЕДУРА СИНХРОНИЗАЦИИ, ВРОДЕ ПРОЦЕДУРЫ В АЛГОРИТМЕ 5.4.6F, НЕ 
ОБЕСПЕЧИВАЕТ НЕПРЕРЫВНОГО ВВОДА/ВЫВОДА, ТАК КАК МЕНЯЮЩЕЕСЯ ВРЕМЯ 
ЧТЕНИЯ ОЗНАЧАЕТ, ЧТО ОПЕРАЦИИ ВВОДА И ВЫВОДА НЕ БУДУТ ОКАНЧИВАТЬСЯ В ОДНО 
ВРЕМЯ. тОЧНЫЙ ОБRЕМ СОВМЕЩЕНИЙ ТРУДНО ОЦЕНИТЬ, И, ВОЗМОЖНО, ЛУЧШЕ 
ПРОМОДЕЛИРОВАТЬ ПРОЦЕСС СЛИЯНИЯ, ЧТОБЫ НАЙТИ КОНСТАНТЫ~$\alpha$ И~$\beta$ 
ДЛЯ ПРИБЛИЖЕННОГО ВРЕМЕНИ СЛИЯНИЯ, КАК В ТЕОРЕМЕ~H.

еСЛИ МЫ ИСПОЛЬЗУЕМ "ПЛАВАЮЩИЕ" БУФЕРЫ (НЕ ПРИПИСАННЫЕ К КОНКРЕТНОМУ ФАЙЛУ),
 ТО ОНИ ДОЛЖНЫ БЫТЬ ОДНОГО РАЗМЕРА, И ТОГДА НЕЛЬЗЯ ПРИМЕНЯТЬ ПРИВЕДЕННУЮ 
ВЫШЕ ТЕХНИКУ РАСПРЕДЕЛЕНИЯ БУФЕРОВ; МОЖНО ТОЛЬКО ВЫБРАТЬ БУФЕРЫ ВЫВОДА 
БОЛЬШЕ, ЧЕМ БУФЕРЫ ВВОДА. еСЛИ ИСПОЛЬЗУЕТСЯ $2P$~БУФЕРОВ ВВОДА 
(ВМЕСТО~$P$), МЫ СОВМЕЩАЕМ ЗНАЧИТЕЛЬНУЮ ДОЛЮ ВРЕМЕНИ ВВОДА, ОДНАКО 
УДВАИВАЕМ ВРЕМЯ ПОИСКА И, ВОЗМОЖНО, НИЧЕГО НЕ ВЫИГРАЕМ; ПО-ВИДИМОМУ, 
ЛУЧШЕ ВСЕГО ИМЕТЬ $P+1$ ИЛИ $P+2$~БУФЕРОВ ВВОДА.
тЕПЕРЬ ЧИТАТЕЛЮ ДОЛЖНО БЫТЬ ЯСНО, ЧТО НИКАКОЙ ЧЕТКОЙ СТРАТЕГИИ ДЛЯ 
ОПТИМАЛЬНОЙ СОРТИРОВКИ НА ДИСКАХ НЕ РАЗРАБОТАНО;
ЧИСЛО ВОЗМОЖНЫХ ВАРИАНТОВ ЗНАЧИТЕЛЬНО ПРЕВЫШАЕТ ЧИСЛО СТРАТЕГИЙ. КОТОРЫЕ 
БЫЛИ ПРОАНАЛИЗИРОВАНЫ ТЕОРЕТИЧЕСКИ. хОТЯ ТЕОРИЯ,
%%442
РАЗВИТАЯ В ЭТОМ ПУНКТЕ, ДАЕТ НЕКОТОРЫЕ ПОЛЕЗНЫЕ ПРЕДСТАВЛЕНИЯ, ВСЕ 
ЕЩЕ ТРЕБУЕТСЯ ЗНАЧИТЕЛЬНЫЙ ОБRЕМ ЭКСПЕРИМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ.

\section *пОДРОБНЕЕ ОБ ОПТИМАЛЬНЫХ ДЕРЕВЬЯХ. в ТЕОРЕМАХ~H И~K ИНТЕРЕСНО 
РАССМОТРЕТЬ КРАЙНИЙ СЛУЧАЙ~$\beta=0$, НЕСМОТРЯ НА ТО ЧТО ПРАКТИЧЕСКИЕ 
СИТУАЦИИ ОБЫЧНО ПРИВОДЯТ К ПАРАМЕТРАМ~$0\le\alpha\le\beta$. кАКОЕ ДЕРЕВО С 
$n$~ЛИСТЬЯМИ ИМЕЕТ НАИМЕНЬШУЮ ВОЗМОЖНУЮ ДЛИНУ СТЕПЕННОГО ПУТИ? лЮБОПЫТНО, 
ЧТО В ЭТОМ СЛУЧАЕ НАИЛУЧШИМ ОКАЗЫВАЕТСЯ ТРЕХПУТЕВОЕ СЛИЯНИЕ.

\proclaim тЕОРЕМА L. дЛИНА СТЕПЕННОГО ПУТИ ДЕРЕВА С $n$~ЛИСТЬЯМИ НИКОГДА 
НЕ МЕНЬШЕ, ЧЕМ
$$
f(n)=\cases{
3qn+2(n-3^q), & ЕСЛИ $2\cdot 3^{q-1}\le n\le 3^q$;\cr
3qn+4(n-3^q), & ЕСЛИ $3^q\le n\le 2\cdot 3^q$.\cr
}
\eqno(11)
$$
тЕРНАРНЫЕ ДЕРЕВЬЯ~$\cJ_n$, ОПРЕДЕЛЕННЫЕ ПРАВИЛАМИ
\picture{рИСУНОК НА СТР. 442}
ИМЕЮТ МИНИМАЛЬНУЮ ДЛИНУ СТЕПЕННОГО ПУТИ.

\proof. вАЖНО ЗАМЕТИТЬ, ЧТО $f (n)$---ВЫПУКЛАЯ ФУНКЦИЯ, Т. Е.
$$
f(n+1)-f(n)\ge f(n)-f(n-1) \rem{ПРИ ВСЕХ $n\ge2$}.
\eqno(13)
$$
эТО СВОЙСТВО СУЩЕСТВЕННО ВВИДУ СЛЕДУЮЩЕЙ ЛЕММЫ.

\proclaim лЕММА с. ФУНКЦИЯ~$g(n)$, ОПРЕДЕЛЕННАЯ НА ПОЛОЖИТЕЛЬНЫХ ЦЕЛЫХ 
ЧИСЛАХ, УДОВЛЕТВОРЯЕТ УСЛОВИЮ
$$
\min_{1\le k\le n} (g(k)+g(n-k))=g(\floor{n/2})+g(\ceil{n/2}), 
\quad n\ge 2,
\eqno (14)
$$
ТОГДА И ТОЛЬКО ТОГДА, КОГДА ОНА ВЫПУКЛАЯ.

\proof. еСЛИ $g(n+1)-g(n)<g(n)- g(n-1)$ ПРИ НЕКОТОРОМ~$n>2$, ТО ИМЕЕМ 
$g(n+1)+g(n-1)<g(n)+g(n)$, ЧТО ПРОТИВОРЕЧИТ~(14). оБРАТНО, ЕСЛИ~(13) 
ИМЕЕТ МЕСТО ДЛЯ~$g$ 
И~$1\le k<n-k$, ТО В СИЛУ 
ВЫПУКЛОСТИ~$g(k+1)+g(n-k-1)\le g(k)+g(n-k)$.\proofend

пОСЛЕДНЮЮ ЧАСТЬ ДОКАЗАТЕЛЬСТВА ЛЕММЫ с МОЖНО РАСПРОСТРАНИТЬ НА 
ЛЮБОЕ~$m\ge2$ И ПОКАЗАТЬ, ЧТО
$$
\min_{n_1+\cdots+n_m=n\atop n_1, \ldots, n_m\ge 1}
 (g(n_1)+\cdots+g(n_m))=g(\floor{n/m})+g(\floor{(n+1)/m})+\cdots
+g(\floor{(n+m-1)/m}),
\eqno(15)
$$
%%443
ЕСЛИ $g$~ВЫПУКЛА. пУСТЬ
$$
f_m(n)=f(\floor{n/m})+f(\floor{(n+1)/m})+\cdots+f(\floor{(n+m-1)/m}).
$$
дОКАЗАТЕЛЬСТВО ТЕОРЕМЫ~L ЗАВЕРШАЕТСЯ ДОКАЗАТЕЛЬСТВОМ ТОГО, 
ЧТО $f_3(n)+3n=f(n)$ И~$f_m(n)+mn\ge f(n)$ ПРИ ВСЕХ~$m\ge2$ (СМ.~УПР.~11).\proofend

бЫЛО БЫ ОЧЕНЬ ХОРОШО, ЕСЛИ БЫ ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ ВСЕГДА ХАРАКТЕРИЗОВАЛИСЬ 
ТАК ЖЕ ЧЕТКО, КАК В ТЕОРЕМЕ~L. нО РЕЗУЛЬТАТЫ ДЛЯ $\alpha=\beta$, КОТОРЫЕ 
МЫ ВИДИМ В ТАБЛ.~1, ПОКАЗЫВАЮТ, ЧТО ФУНКЦИЯ~$A_1(n)$ НЕ ВСЕГДА ВЫПУКЛА. нА 
САМОМ ДЕЛЕ ТАБЛ.~1 ДОСТАТОЧНО, ЧТОБЫ ОПРОВЕРГНУТЬ БОЛЬШИНСТВО ПРОСТЫХ 
ПРЕДПОЛОЖЕНИЙ ОБ ОПТИМАЛЬНЫХ ДЕРЕВЬЯХ! мЫ, ОДНАКО, МОЖЕМ СПАСТИ ЧАСТЬ 
ТЕОРЕМЫ~L ДЛЯ СЛУЧАЯ ПРОИЗВОЛЬНЫХ~$\alpha$ И~$\beta$. м.~шЛЮМБЕРГЕР 
И ж.~вИЙЕМАН ПОКАЗАЛИ, ЧТО \emph{ВЫСОКИХ} ПОРЯДКОВ СЛИЯНИЯ ВСЕГДА МОЖНО 
ИЗБЕЖАТЬ.

\proclaim тЕОРЕМА M. еСЛИ ДАНЫ~$\alpha$ И~$\beta$, КАК В ТЕОРЕМЕ~H, ТО 
СУЩЕСТВУЕТ ОПТИМАЛЬНОЕ ДЕРЕВО, В КОТОРОМ СТЕПЕНЬ ЛЮБОГО УЗЛА НЕ ПРЕВОСХОДИТ
$$
d(\alpha, \beta)=\ceil{\min_{k\ge1}\left(k+\left(1+{1\over k}\right)
\left(1+{\beta\over\alpha}\right)\right)}.
\eqno(17)
$$

\proof. пУСТЬ $n_1$,~\dots, $n_m$---ПОЛОЖИТЕЛЬНЫЕ ЦЕЛЫЕ ЧИСЛА, ТАКИЕ, ЧТО 
$n_1+\cdots+n_m=n$, $A(n_1)+\cdots+A(n_m)= A_m(n)$, 
$n_1\le \ldots \le n_m$, И ПРЕДПОЛОЖИМ, ЧТО $m\ge d(\alpha, \beta)+1$. 
пУСТЬ $k$---ТО ЗНАЧЕНИЕ, ПРИ КОТОРОМ ДОСТИГАЕТСЯ МИНИМУМ В (17); ПОКАЖЕМ, ЧТО
$$
\alpha n(m-k)+\beta n+A_{m-k}(n)\le \alpha m n +\beta n+A_m(n),
\eqno(18)
$$
И, СЛЕДОВАТЕЛЬНО, МИНИМУМ В (4) ВСЕГДА ДОСТИГАЕТСЯ ПРИ НЕКОТОРОМ
$m\le d(\alpha, \beta)$.

пО ОПРЕДЕЛЕНИЮ, ПОСКОЛЬКУ $m\ge k+2$, МЫ ДОЛЖНЫ ИМЕТЬ
$$
\eqalign{
A_{m-k}(n) &\le A_1(n_1+\cdots+n_{k+1})+A_1(n_{k+2})+\cdots
+A_1(n_m)\le\cr
&\le \alpha(n_1+\cdots+n_{k+1})(k+1)+\beta(n_1+\cdots+n_{k+1})+\cr
&\phantom{\le}+A_1(n_1)+\cdots+A_1(n_m)=\cr
&=(\alpha(k+1)+\beta)(n_1+\cdots+n_{k+1})+A_m(n)\le\cr
&\le(\alpha(k+1)+\beta)(k+1)n/m+A_m(n),\cr
}
$$
ОТСЮДА (18) ЛЕГКО ВЫВОДИТСЯ. (тЩАТЕЛЬНОЕ РАССМОТРЕНИЕ ЭТОГО 
ДОКАЗАТЕЛЬСТВА ПОКАЗЫВАЕТ, ЧТО ОЦЕНКА~(17) ЯВЛЯЕТСЯ "НАИЛУЧШЕЙ ИЗ 
ВОЗМОЖНЫХ" В ТОМ СМЫСЛЕ, ЧТО НЕКОТОРЫЕ ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ ДОЛЖНЫ ИМЕТЬ 
УЗЛЫ СТЕПЕНИ~$d(\alpha, \beta)$; СМ. УПР.~13.) \proofend

пОСТРОЕНИЕ В ТЕОРЕМЕ~K ТРЕБУЕТ $O(N^2)$~ЯЧЕЕК ПАМЯТИ И $O(N^2\log 
N)$~ШАГОВ ДЛЯ ВЫЧИСЛЕНИЯ $A_m(n)$ ПРИ $1\le m\le n\le N$, a
%%444
В ТЕОРЕМЕ~M ПОКАЗАНО, ЧТО ТРЕБУЕТСЯ ТОЛЬКО $O(N)$~ЯЧЕЕК И $O(N^2)$~ШАГОВ. 
шЛЮМБЕРГЕР И вИЙЕМАН ОТКРЫЛИ ЕЩЕ НЕСКОЛЬКО ОЧЕНЬ ИНТЕРЕСНЫХ СВОЙСТВ 
ОПТИМАЛЬНЫХ ДЕРЕВЬЕВ 
[Optimal disk merge patterns, {\sl Acta Informatica,\/} {\bf 3} (1973), 25--36].

\section иСПОЛЬЗОВАНИЕ СЦЕПЛЕНИЯ. м. а. гОТЦ 
[{\sl CACM,\/} {\bf 6} (1963), 245--248]
ПРЕДЛОЖИЛ ИНТЕРЕСНЫЙ СПОСОБ, ПРИ КОТОРОМ ОТДЕЛЬНЫЕ ДОРОЖКИ СВЯЗЫВАЮТСЯ 
ВМЕСТЕ И БЛАГОДАРЯ ЭТОМУ ИСКЛЮЧАЕТСЯ ПОИСК ПРИ ВЫВОДЕ. дЛЯ РЕАЛИЗАЦИИ ЕГО 
ИДЕИ ТРЕБУЕТСЯ ПОЧТИ НЕВООБРАЗИМЫЙ НАБОР ПРОГРАММ, УПРАВЛЯЮЩИХ ДИСКАМИ, 
НО САМА ИДЕЯ, КРОМЕ СОРТИРОВКИ, ПРИМЕНИМА ВО МНОГИХ ДРУГИХ ЗАДАЧАХ, И 
ПОЭТОМУ ОНА МОЖЕТ ПРИВЕСТИ К ВЕСЬМА ЦЕННЫМ МЕТОДАМ ОБЩЕГО НАЗНАЧЕНИЯ.

иДЕЯ ПРОСТА. вМЕСТО РАЗМЕЩЕНИЯ ДОРОЖЕК ПОСЛЕДОВАТЕЛЬНО ВНУТРИ ЦИЛИНДРОВ 
ДИСКА МЫ СВЯЗЫВАЕМ ИХ ВМЕСТЕ И ХРАНИМ СПИСКИ СВОБОДНОГО ПРОСТРАНСТВА ПО 
ОДНОМУ ДЛЯ КАЖДОГО ЦИЛИНДРА. кОГДА ПРИХОДИТ ВРЕМЯ ВЫВЕСТИ ДОРОЖКУ 
ИНФОРМАЦИИ, МЫ ЗАПИСЫВАЕМ ЕЕ В ТЕКУЩИЙ ЦИЛИНДР (В ТОТ, ГДЕ ОКАЗАЛСЯ 
ДЕРЖАТЕЛЬ ГОЛОВОК), ЕСЛИ ЭТОТ ЦИЛИНДР НЕ ПОЛОН. пРИ ЭТОМ ВРЕМЯ 
ПОИСКА ОБЫЧНО СВОДИТСЯ НА НЕТ.

зДЕСЬ НАС ПОДСТЕРЕГАЕТ ЛОВУШКА. дЕЛО В ТОМ, ЧТО МЫ НЕ МОЖЕМ ЗАПИСЫВАТЬ 
ССЫЛКУ НА СЛЕДУЮЩУЮ ДОРОЖКУ ВНУТРИ САМОЙ ДОРОЖКИ, ПОСКОЛЬКУ НЕОБХОДИМАЯ 
ДЛЯ ЭТОГО ИНФОРМАЦИЯ В НУЖНЫЙ МОМЕНТ НЕ ИЗВЕСТНА. (мЫ МОГЛИ БЫ, ЕСЛИ ЭТО 
НАС УСТРОИТ, ЗАПИСЫВАТЬ ССЫЛКУ НА ПРЕДЫДУЩУЮ ДОРОЖКУ И НА 
СЛЕДУЮЩЕМ ПРОХОДЕ ЧИТАТЬ ФАЙЛ В ОБРАТНОМ НАПРАВЛЕНИИ.) мОЖНО 
ХРАНИТЬ ОТДЕЛЬНУЮ ТАБЛИЦУ АДРЕСОВ СВЯЗИ ДЛЯ ДОРОЖЕК КАЖДОГО ФАЙЛА,
 ВОЗМОЖНО, ЧАСТИЧНО НА САМОМ ДИСКЕ. сПИСКИ СВОБОДНОГО-ПРОСТРАНСТВА МОЖНО 
КОМПАКТНО ПРЕДСТАВИТЬ С ПОМОЩЬЮ БИТОВЫХ ТАБЛИЦ, ГДЕ 1000~БИТОВ УКАЗЫВАЮТ 
ЗАНЯТОСТЬ ИЛИ НЕЗАНЯТОСТЬ 1000~ДОРОЖЕК.

\qsection пОМОЖЕТ ЛИ СОРТИРОВКА КЛЮЧЕЙ? еСЛИ ЗАПИСИ ДЛИННЫЕ, А КЛЮЧИ 
КОРОТКИЕ, ВЕСЬМА ЗАМАНЧИВО СОЗДАТЬ НОВЫЙ ФАЙЛ, СОСТОЯЩИЙ ТОЛЬКО ИЗ КЛЮЧЕЙ 
ВМЕСТЕ С ПОРЯДКОВЫМИ НОМЕРАМИ, ОПРЕДЕЛЯЮЩИМИ ИХ ПЕРВОНАЧАЛЬНОЕ ПОЛОЖЕНИЕ В 
ФАЙЛЕ. пОСЛЕ СОРТИРОВКИ ЭТОГО ФАЙЛА КЛЮЧЕЙ МОЖНО ЗАМЕНИТЬ КЛЮЧИ 
ПОСЛЕДОВАТЕЛЬНЫМИ ЧИСЛАМИ~$1$, $2$,~\dots. зАТЕМ ЭТОТ НОВЫЙ ФАЙЛ МОЖНО 
ОТСОРТИРОВАТЬ ПО ПОЛОЖЕНИЮ В ПЕРВОНАЧАЛЬНОМ ФАЙЛЕ, И МЫ ПОЛУЧИМ 
УДОБНОЕ ОПИСАНИЕ ТОГО, КАК "РАСТАСОВАТЬ" ЗАПИСИ, ЧТОБЫ ПЕРЕРАЗМЕСТИТЬ ИХ В 
ТРЕБУЕМОМ ПОРЯДКЕ.

сХЕМАТИЧЕСКИ ПРЕДСТАВИМ ПРОЦЕСС ТАК:
\halign{
#\hfill&#\hfill\cr
a) ИСХОДНЫЙ ФАЙЛ           & $(K_1, I_1)$ $(K_2, I_2)$ \dots $(K_N, I_N)$ ДЛИННЫЙ;\cr
b) КЛЮЧЕВОЙ ФАЙЛ          & $(K_1, 1)$ $(K_2, 2)$ \dots $(K_N, N)$ КОРОТКИЙ;\cr
c) ОТСОРТИРОВАННЫЙ (b)& $(K_{p_1}, p_1)$ $(K_{p_2}, p_2)$\dots $(K_{p_N}, p_N)$ КОРОТКИЙ;\cr
%%445
d) ОТРЕДАКТИРОВАННЫЙ (С) & $(1, p_1)$ $(2, p_2)$ \dots $(N, p_N)$ КОРОТКИЙ;\cr
e) ОТСОРТИРОВАННЫЙ   (d)&  $(q_1, 1)$ $(q_2, 2)$ \dots $(q_N, N)$ КОРОТКИЙ;\cr
f) ОТРЕДАКТИРОВАННЫЙ (a) & $(q_1, I_1)$  $(q_2, I_2)$ \dots $(q_N, I_n)$ ДЛИННЫЙ.\cr
}

\noindent зДЕСЬ $p_j=k$ ТОГДА И ТОЛЬКО ТОГДА, КОГДА $q_k=j$; ДВА 
ПРОЦЕССА СОРТИРОВКИ В СТАДИЯХ (c) И (c) СРАВНИТЕЛЬНО БЫСТРЫЕ (ИНОГДА МОЖНО 
ОБОЙТИСЬ ВНУТРЕННЕЙ СОРТИРОВКОЙ), ТАК КАК ЗАПИСИ НЕ СЛИШКОМ ДЛИННЫЕ. нА 
СТАДИИ (f) МЫ СВЕЛИ ЗАДАЧУ К СОРТИРОВКЕ ФАЙЛА, КЛЮЧИ КОТОРОГО---ПРОСТО ЧИСЛА 
$\{1, 2,~\ldots, N\}$; КАЖДАЯ ЗАПИСЬ ТЕПЕРЬ ОПРЕДЕЛЯЕТ В ТОЧНОСТИ ТО МЕСТО,
КУДА ЕЕ СЛЕДУЕТ ПЕРЕМЕСТИТЬ.

пРОБЛЕМА ВНЕШНЕГО ПЕРЕРАЗМЕЩЕНИЯ, ОСТАЮЩАЯСЯ ПОСЛЕ СТАДИИ (f), КАЖЕТСЯ 
НА ПЕРВЫЙ ВЗГЛЯД ТРИВИАЛЬНОЙ, НО ФАКТИЧЕСКИ ОНА ОЧЕНЬ СЛОЖНА, И ВСЕ ЕЩЕ НЕ 
НАЙДЕНО НИ ОДНОГО ДЕЙСТВИТЕЛЬНО ХОРОШЕГО АЛГОРИТМА (СУЩЕСТВЕННО ЛУЧШЕГО, 
ЧЕМ СОРТИРОВКА). мЫ, ОЧЕВИДНО, МОГЛИ БЫ ВЫПОЛНИТЬ ПЕРЕРАЗМЕЩЕНИЕ ЗА 
$N$~ШАГОВ, ПЕРЕМЕЩАЯ ВСЯКИЙ РАЗ ПО ОДНОЙ ЗАПИСИ; ДЛЯ 
ДОСТАТОЧНО БОЛЬШОГО~$N$ ЭТО ЛУЧШЕ, ЧЕМ $N\log N$ В МЕТОДАХ СОРТИРОВКИ. 
нО $N$ НИКОГДА НЕ БЫВАЕТ ТАКИМ БОЛЬШИМ; $N$ ПОИСКОВ ПРОСТО НЕРЕАЛЬНЫ!

к ОТРЕДАКТИРОВАННЫМ ЗАПИСЯМ МОЖНО ЭФФЕКТИВНО ПРИМЕНЯТЬ КАКОЙ-ЛИБО МЕТОД 
ПОРАЗРЯДНОЙ СОРТИРОВКИ, ТАК КАК КЛЮЧИ ИМЕЮТ СТРОГО РАВНОМЕРНОЕ 
РАСПРЕДЕЛЕНИЕ. нА МНОГИХ ВЫСОКОСКОРОСТНЫХ эвм С ВЫСОКОСКОРОСТНЫМИ 
ПЕРИФЕРИЙНЫМИ УСТРОЙСТВАМИ ВРЕМЯ ВЫЧИСЛЕНИЙ ДЛЯ ВОСЬМИПУТЕВОГО 
РАСПРЕДЕЛЕНИЯ ЗНАЧИТЕЛЬНО МЕНЬШЕ, ЧЕМ ВРЕМЯ ВЫЧИСЛЕНИЙ ДЛЯ 
ВОСЬМИПУТЕВОГО СЛИЯНИЯ; СЛЕДОВАТЕЛЬНО, РАСПРЕДЕЛИТЕЛЬНАЯ СОРТИРОВКА 
МОЖЕТ БЫТЬ НАИЛУЧШЕЙ ИЗ ВСЕХ ПРОЦЕДУР (СМ.~П.~5.4.7, А ТАКЖЕ УПР.~17).

нО, ПО-ВИДИМОМУ, БЕССМЫСЛЕННО ПРОВОДИТЬ СОРТИРОВКУ КЛЮЧЕЙ ЛИШЬ ДЛЯ ТОГО,
 ЧТОБЫ ВЫПОЛНИТЬ ЗАТЕМ ПОЛНУЮ СОРТИРОВКУ! оДНА ИЗ ПРИЧИН НЕОЖИДАННОЙ 
ТРУДНОСТИ ПРОБЛЕМЫ ВНЕШНЕГО ПЕРЕРАЗМЕЩЕНИЯ БЫЛА ОТКРЫТА р.~у.~фЛОЙДОМ, 
КОТОРЫЙ НАШЕЛ НЕТРИВИАЛЬНУЮ НИЖНЮЮ ГРАНИЦУ ДЛЯ ЧИСЛА ПОИСКОВ, ТРЕБУЕМЫХ,
 ЧТОБЫ ПЕРЕСТАВИТЬ ЗАПИСИ В ДИСКОВОМ ФАЙЛЕ 
[Complexity of Computer Computations (New York, Plenum, 1972), 105--109].

рЕЗУЛЬТАТ фЛОЙДА УДОБНО ОПИСАТЬ, ВОСПОЛЬЗОВАВШИСЬ АНАЛОГИЕЙ С ЛИФТОМ, 
КАК В П.~5.4.8; НА ЭТОТ РАЗ МЫ ХОТИМ НАЙТИ ГРАФИК РАБОТЫ ЛИФТА, 
МИНИМИЗИРУЮЩИЙ ЧИСЛО ОСТАНОВОК, А НЕ ПРОЙДЕННОЕ РАССТОЯНИЕ. (мИНИМИЗАЦИЯ 
ЧИСЛА \emph{ОСТАНОВОК} НЕ ВПОЛНЕ ЭКВИВАЛЕНТНА НАХОЖДЕНИЮ АЛГОРИТМА 
ПЕРЕРАЗМЕЩЕНИЯ С МИНИМАЛЬНЫМ ЧИСЛОМ ПОИСКОВ, ТАК КАК ОДНА ОСТАНОВКА 
ОБRЕДИНЯЕТ ВХОД В ЛИФТ С ВЫХОДОМ ИЗ НЕГО; ОДНАКО РАЗНИЦА НЕ СЛИШКОМ ВЕЛИКА,
  И МЫ ВОСПОЛЬЗУЕМСЯ КРИТЕРИЕМ МИНИМИЗАЦИИ ОСТАНОВОК, ЧТОБЫ ПОЯСНИТЬ 
ОСНОВНЫЕ ИДЕИ.)
%% 446
бУДЕМ ИСПОЛЬЗОВАТЬ ФУНКЦИЮ "ДИСКРЕТНОЙ ЭНТРОПИИ"
$$
F(n)=\sum_{1<k\le n}(\ceil{\log_2 k}+1)=B(n)+n-1
=n\ceil{\log_2 n}-2^{\ceil{\log_2 n}}+n,
\eqno(19)
$$
ГДЕ $B(n)$ ЕСТЬ ФУНКЦИЯ "БИНАРНОЙ ВСТАВКИ" (СМ. ФОРМУЛУ (5.3.1-3)). 
сОГЛАСНО (5.3.1-33), ФУНКЦИЯ $F(n)$ ЕСТЬ НЕ ЧТО ИНОЕ, КАК МИНИМАЛЬНАЯ 
ДЛИНА ВНЕШНЕГО ПУТИ БИНАРНОГО ДЕРЕВА С $n$~ЛИСТЬЯМИ, И  
$$
n\log_2 n\le F(n)\le n\log_2 n+0.0861n.
\eqno(20)
$$
тАК КАК $F (n)$ ВЫПУКЛА И УДОВЛЕТВОРЯЕТ 
УСЛОВИЮ~$F(n)=n+F(\floor{n/2})+F(\ceil{n/2})$, ТО ПО ЛЕММЕ~C
$$
F(n)\le F(k)+F(n-k)+n \rem{ПРИ $0\le k\le n$.}
\eqno(21)
$$
эТО СООТНОШЕНИЕ ВЫТЕКАЕТ ТАКЖЕ ИЗ ПРЕДСТАВЛЕНИЯ $F$ В ВИДЕ ДЛИНЫ ВНЕШНЕГО 
ПУТИ; В ДАЛЬНЕЙШЕМ ОНО ОКАЖЕТСЯ РЕШАЮЩИМ ФАКТОМ.

кАК И В П.~5.4.8, МЫ БУДЕМ ПРЕДПОЛАГАТЬ, ЧТО ЛИФТ ВМЕЩАЕТ $b$~ЧЕЛОВЕК, 
КАЖДЫЙ ЭТАЖ ВМЕЩАЕТ $c$~ЧЕЛОВЕК И ИМЕЕТСЯ $n$~ЭТАЖЕЙ. пУСТЬ $s_{ij}$---ЧИСЛО 
ЛЮДЕЙ, НАХОДЯЩИХСЯ В ДАННЫЙ МОМЕНТ НА ЭТАЖЕ~$i$ И СТРЕМЯЩИХСЯ ПОПАСТЬ НА 
ЭТАЖ~$j$. пО ОПРЕДЕЛЕНИЮ 
\emph{ОЦЕНКА СОВМЕСТНОСТИ} ЛЮБОГО РАСПОЛОЖЕНИЯ ЛЮДЕЙ В ЗДАНИИ 
ЕСТЬ~$\sum_{1\le i,j\le n} F(s_{ij})$.

пРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО $b=c=n=6$ И ЧТО ПЕРВОНАЧАЛЬНО 36~ЧЕЛОВЕК 
СЛЕДУЮЩИМ ОБРАЗОМ РАСПРЕДЕЛЕНЫ МЕЖДУ ЭТАЖАМИ:
{\obeyspaces
$$
\vbox{
\line{\tt\indent \]\]\]\]\]\]}
\line{\tt\indent 123456 123456 123456 123456 123456 123456 \hfill \rm (22)}
}
$$
}
лИФТ ПУСТ И НАХОДИТСЯ НА ЭТАЖЕ 1; "\]" ОБОЗНАЧАЕТ СВОБОДНОЕ МЕСТО. нА 
КАЖДОМ ЭТАЖЕ НАХОДИТСЯ ЧЕЛОВЕК, СТРЕМЯЩИЙСЯ ПОПАСТЬ НА ПРОИЗВОЛЬНЫЙ ЭТАЖ,
 ПОЭТОМУ ВЕЛИЧИНЫ~$s_{ij}$. РАВНЫ~1 И ОЦЕНКА СОВМЕСТНОСТИ РАВНА~0. еСЛИ 
ТЕПЕРЬ ЛИФТ ОТВЕЗЕТ 6~ЧЕЛОВЕК НА ЭТАЖ~2, ТО МЫ ПОЛУЧИМ РАСПОЛОЖЕНИЕ
{\obeyspaces
$$
\vbox{
\line{\tt\indent        123456}
\line{\tt\indent \]\]\]\]\]\] 123456 123456 123456 123456 123456 \hfill 
\rm (23)}
}
$$
}
И ОЦЕНКА СОВМЕСТНОСТИ СТАНЕТ РАВНА $6F(0)+24F(1)+6F(2)=12$. дОПУСТИМ, 
ЛИФТ ПЕРЕВЕЗЕТ |1|, |1|, |2|, |3|, |3|, |4| НА ЭТАЖ~3:
{\obeyspaces
$$
\vbox{
\line{\tt\indent               112334}
\line{\tt\indent \]\]\]\]\]\] 245566 123456 123456 123456 123456 \hfill 
\rm (24)}
}
$$
}
%%447
оЦЕНКА СОВМЕСТНОСТИ ИЗМЕНИЛАСЬ ДО $4F(2)+2F(3)=18$. кОГДА КАЖДЫЙ ЧЕЛОВЕК 
БУДЕТ В КОНЦЕ КОНЦОВ ПЕРЕВЕЗЕН К СВОЕМУ МЕСТУ НАЗНАЧЕНИЯ, ОЦЕНКОЙ 
СОВМЕСТНОСТИ БУДЕТ $6F(6)=96$.

фЛОЙД ЗАМЕТИЛ, ЧТО ОЦЕНКА СОВМЕСТНОСТИ НИКОГДА НЕ УВЕЛИЧИВАЕТСЯ БОЛЬШЕ, 
ЧЕМ НА $b+c$ ЗА ОДНУ ОСТАНОВКУ, ТАК КАК МНОЖЕСТВО ИЗ $s$~ЛЮДЕЙ С РАВНЫМ 
НАЗНАЧЕНИЕМ, ОБRЕДИНЯЯСЬ С АНАЛОГИЧНЫМ МНОЖЕСТВОМ МОЩНОСТИ~$s'$, 
УВЕЛИЧИВАЕТ ОЦЕНКУ НА $F(s+s')-F(s)-F(s')\le s+s'$. тАКИМ ОБРАЗОМ, ИМЕЕМ 
СЛЕДУЮЩИЙ РЕЗУЛЬТАТ.

\proclaim тЕОРЕМА~F. пУСТЬ $t$---ОПРЕДЕЛЕННАЯ ВЫШЕ ОЦЕНКА СОВМЕСТНОСТИ 
НАЧАЛЬНОГО РАСПОЛОЖЕНИЯ ЛЮДЕЙ. лИФТ ДОЛЖЕН СДЕЛАТЬ ПО КРАЙНЕЙ МЕРЕ
$$
\ceil{(nF(c)-t)/(b+c)}
$$
ОСТАНОВОК, ЧТОБЫ ДОСТАВИТЬ ВСЕХ ЛЮДЕЙ К ИХ МЕСТУ НАЗНАЧЕНИЯ.\endmark


сФОРМУЛИРУЕМ ЭТОТ РЕЗУЛЬТАТ ПРИМЕНИТЕЛЬНО К ДИСКАМ. дОПУСТИМ, ИМЕЕТСЯ 
$N$~ЗАПИСЕЙ ПО $B$ В КАЖДОМ БЛОКЕ, И ПРЕДПОЛОЖИМ, ЧТО ВО ВНУТРЕННЕЙ 
ПАМЯТИ ОДНОВРЕМЕННО ПОМЕЩАЕТСЯ $M$~ЗАПИСЕЙ. пРИ КАЖДОМ ЧТЕНИИ С ДИСКА ОДИН 
БЛОК ПЕРЕНОСИТСЯ В НАМЯТЬ, А ПРИ КАЖДОЙ ЗАПИСИ ОДИН БЛОК ПОМЕЩАЕТСЯ НА 
ДИСК, И $s_{ij}$ ЕСТЬ ЧИСЛО ЗАПИСЕЙ В БЛОКЕ~$i$, ПРИНАДЛЕЖАЩИХ 
БЛОКУ~$j$. еСЛИ $N\ge B^2$, ТО СУЩЕСТВУЕТ НАЧАЛЬНОЕ РАСПОЛОЖЕНИЕ, ДЛЯ 
КОТОРОГО ВСЕ $s_{ij}\le 1$, И, СЛЕДОВАТЕЛЬНО, ДЛЯ ПЕРЕРАЗМЕЩЕНИЯ 
ЗАПИСЕЙ НЕОБХОДИМО ПРОЧИТАТЬ ПО КРАЙНЕЙ МЕРЕ 
$(N/B)F(B)/M\approx (N \log_2 B)/M$~БЛОКОВ. (еСЛИ $B$ ВЕЛИКО, ТО 
МНОЖИТЕЛЬ~$\log_2 B$ ДЕЛАЕТ ЭТУ НИЖНЮЮ ОЦЕНКУ НЕТРИВИАЛЬНОЙ, НО ЕСЛИ $B=1$,
 ТО НИЖНЮЮ ОЦЕНКУ, ОЧЕВИДНО, МОЖНО УЛУЧШИТЬ.)

\excercises
\ex[M22] в ТЕКСТЕ ОБRЯСНЯЕТСЯ МЕТОД, С ПОМОЩЬЮ КОТОРОГО СРЕДНЕЕ 
ВРЕМЯ ОЖИДАНИЯ, ТРЕБУЕМОЕ ДЛЯ ЧТЕНИЯ ДОЛИ~$x$ ДОРОЖКИ, УМЕНЬШАЕТСЯ 
С~${1\over2}$ 
ДО~${1\over2}(1-x^2)$~ОБОРОТОВ. эТО МИНИМАЛЬНО ВОЗМОЖНОЕ ВРЕМЯ, КОГДА 
ИМЕЕТСЯ ОДИН ДЕРЖАТЕЛЬ ГОЛОВОК. кАКОВО СООТВЕТСТВУЮЩЕЕ МИНИМАЛЬНОЕ ВРЕМЯ 
ОЖИДАНИЯ, ЕСЛИ ИМЕЮТСЯ \emph{ДВА} ДЕРЖАТЕЛЯ ГОЛОВОК, РАЗНЕСЕННЫЕ НА 
$180^\circ$ (В ПРЕДПОЛОЖЕНИИ, ЧТО В ЛЮБОЙ МОМЕНТ ДАННЫЕ МОЖЕТ ПЕРЕДАВАТЬ 
ТОЛЬКО ОДИН ИЗ ДЕРЖАТЕЛЕЙ)?

\ex[M30] (э.~г.~кОНХЕЙМ.) цЕЛЬ ЭТОЙ ЗАДАЧИ---ИССЛЕДОВАТЬ, НА 
КАКОЕ РАССТОЯНИЕ ДОЛЖЕН ПЕРЕМЕСТИТЬСЯ ДЕРЖАТЕЛЬ ГОЛОВОК ВО ВРЕМЯ СЛИЯНИЯ 
ФАЙЛОВ, РАСПОЛОЖЕННЫХ "ОРТОГОНАЛЬНО" К ЦИЛИНДРАМ дОПУСТИМ, ИМЕЕТСЯ 
$P$~ФАЙЛОВ, КАЖДЫЙ ИЗ КОТОРЫХ СОДЕРЖИТ $L$~БЛОКОВ ЗАПИСЕЙ, И ПРЕДПОЛОЖИМ,
ЧТО ПЕРВЫЙ БЛОК КАЖДОГО ФАЙЛА НАХОДИТСЯ НА ЦИЛИНДРЕ~1, ВТОРОЙ---НА 
ЦИЛИНДРЕ~2 И Т~Д дВИЖЕНИЕМ ДЕРЖАТЕЛЯ ГОЛОВОК ВО ВРЕМЯ СЛИЯНИЯ УПРАВЛЯЕТ 
ОТНОСИТЕЛЬНЫЙ ПОРЯДОК ПОСЛЕДНИХ КЛЮЧЕЙ КАЖДОГО БЛОКА; СЛЕДОВАТЕЛЬНО, 
МОЖНО ИЗОБРАЗИТЬ СИТУАЦИЮ СЛЕДУЮЩИМ СПОСОБОМ, УДОБНЫМ ДЛЯ МАТЕМАТИЧЕСКОЙ
%%448
ИНТЕРПРЕТАЦИИ. рАССМОТРИМ МНОЖЕСТВО ИЗ $PL$ УПОРЯДОЧЕННЫХ ПАР
$$
\matrix{
(a_{11},1) & (a_{21},1) & \ldots & (a_{P1},1) \cr
(a_{12},2) & (a_{22},2) & \ldots & (a_{P2},2) \cr
\vdots & \vdots & & \vdots \cr
(a_{1L},L) & (a_{2L},L) & \ldots & (a_{PL},L) \cr
}
$$
ГДЕ МНОЖЕСТВО $\{\, a_{ij} \mid 1\le i\le P, 1\le j\le L\,\}$ 
СООТВЕТСТВУЕТ МНОЖЕСТВУ ЧИСЕЛ $\{\,1, 2, \ldots, PL\,\}$ В НЕКОТОРОМ 
ПОРЯДКЕ И $a_{ij}<a_{i,j+1}$ ПРИ $1\le j<L$ (СТРОКИ ПРЕДСТАВЛЯЮТ ЦИЛИНДРЫ, 
СТОЛБЦЫ---ИСХОДНЫЕ ФАЙЛЫ). оТСОРТИРУЕМ ПАРЫ ПО ИХ ПЕРВЫМ КОМПОНЕНТАМ, И 
ПУСТЬ ПОЛУЧИВШЕЙСЯ ПОСЛЕДОВАТЕЛЬНОСТЬЮ БУДЕТ $(1, j_1)$ $(2, j_2)$ \dots{} 
$(PL, j_{PL})$. пОКАЖИТЕ, ЧТО ЕСЛИ ВСЕ $(PL)!/L!^P$ ВОЗМОЖЛЫХ 
НАБОРОВ~$a_{ij}$ РАВНОВЕРОЯТНЫ, ТО СРЕДНЕЕ ЗНАЧЕНИЕ
$$
\abs{j_2-j_1}+\abs{j_3-j_2}+\cdots+\abs{j_{PL}-j_{PL-1}}
$$
РАВНО
$$
(L-1)\left(1+(P-1)2^{2L-2}/\perm{2L}{L}\right).
$$
[\emph{уКАЗАНИЕ:} СМ. УПР. 5.2.1-14 ] зАМЕТИМ, ЧТО ПРИ  $L\to\infty$ ЭТО 
ЗНАЧЕНИЕ АСИМПТОТИЧЕСКИ РАВНО ${1\over4}(P-1)L\sqrt{\pi L}$.

\ex[м15] пРЕДПОЛОЖИМ, ЧТО ОГРАНИЧЕННЫЙ РАЗМЕР ВНУТРЕННЕЙ ПАМЯТИ ДЕЛАЕТ 
НЕЖЕЛАТЕЛЬНЫМ $10\hbox{-ПУТЕВОЕ}$ СЛИЯНИЕ. кАК МОЖНО ИЗМЕНИТЬ 
РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ (3), (4), (5), ЧТОБЫ $A_1(n)$ СТАЛО МИНИМАЛЬНЫМ 
ЗНАЧЕНИЕМ~$\alpha D(\cJ)+\beta E(\cJ)$ СРЕДИ ВСЕХ ДЕРЕВЬЕВ~$\cJ$ С 
$n$~ЛИСТЬЯМИ, НЕ ИМЕЮЩИХ УЗЛОВ СТЕПЕНИ, БОЛЬШЕЙ ЧЕМ~9?

\rex[м21] (a) вЫВЕДИТЕ ФОРМУЛУ, АНАЛОГИЧНУЮ (2), ДЛЯ ВРЕМЕНИ ВЫПОЛНЕНИЯ 
$P\hbox{-ПУТЕВОГО}$ СЛИЯНИЯ $L$~ЛИТЕР, ЕСЛИ ИСПОЛЬЗУЕТСЯ ВИДОИЗМЕНЕННАЯ 
ФОРМА КВАДРАТИЧНОГО РАСПРЕДЕЛЕНИЯ БУФЕРОВ%
\note{1}{сМ. ТАКЖЕ ФОРМУЛУ (9).---{\sl пРИМ. РЕД.\/}}: ВСЕ $P$~БУФЕРОВ ВВОДА 
ДОЛЖНЫ ИМЕТЬ РАВНЫЕ ДЛИНЫ, А РАЗМЕР БУФЕРА ВЫВОДА СЛЕДУЕТ ВЫБРАТЬ ТАК, 
ЧТОБЫ МИНИМИЗИРОВАТЬ ВРЕМЯ ПОИСКА.

(b) пОКАЖИТЕ, ЧТО ПОСТРОЕНИЕ В ТЕОРЕМЕ~K МОЖНО ИЗМЕНИТЬ ТАК, ЧТО 
ПОЛУЧИТСЯ СХЕМА СЛИЯНИЯ, КОТОРАЯ БУДЕТ ОПТИМАЛЬНОЙ В СМЫСЛЕ ВАШЕЙ 
ФОРМУЛЫ ИЗ ЧАСТИ~(a).

\ex[м20] еСЛИ ИСПОЛЬЗУЮТСЯ ДВА ДИСКА, ПРИЧЕМ ЧТЕНИЕ С ОДНОГО СОВМЕЩАЕТСЯ 
С ЗАПИСЬЮ НА ДРУГОЙ, ТО МЫ НЕ МОЖЕМ ПРИМЕНЯТЬ СХЕМУ СЛИЯНИЯ, ПОДОБНУЮ 
ПРЕДСТАВЛЕННОЙ НА РИС.~93, ТАК КАК НЕКОТОРЫЕ ЛИСТЬЯ НАХОДЯТСЯ НА ЧЕТНЫХ 
УРОВНЯХ, А ДРУГИЕ НА НЕЧЕТНЫХ. пОКАЖИТЕ, КАК ИЗМЕНИТЬ ПОСТРОЕНИЕ В 
ТЕОРЕМЕ~K, ЧТОБЫ ПОЛУЧАЛИСЬ ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ С УЧЕТОМ ОГРАНИЧЕНИЯ, 
ЧТО ВСЕ ЛИСТЬЯ НАХОДЯТСЯ НА ЧЕТНЫХ УРОВНЯХ ИЛИ ВСЕ НА НЕЧЕТНЫХ.

\rex[22] нАЙДИТЕ ДЕРЕВО, ОПТИМАЛЬНОЕ В СМЫСЛЕ УПР.~6, ЕСЛИ~$n=23$ 
И~$\alpha=\beta=1$. (вОЗМОЖНО, У ВАС ПОЯВИТСЯ ЖЕЛАНИЕ ПРИБЕГНУТЬ К ПОМОЩИ эвм.)

\rex[м24] еСЛИ ДЛИНЫ НАЧАЛЬНЫХ ОТРЕЗКОВ НЕ РАВНЫ, ТО НАИЛУЧШАЯ 
СХЕМА СЛИЯНИЯ (В СМЫСЛЕ ТЕОРЕМЫ~H) МИНИМИЗИРУЕТ $\alpha D(\cJ)+\beta 
E(\cJ)$, ГДЕ $D(\cJ)$ И~$E(\cJ)$ ТЕПЕРЬ ПРЕДСТАВЛЯЮТ СОБОЙ ВЗВЕШЕННЫЕ 
ДЛИНЫ ПУТЕЙ: КАЖДОМУ ЛИСТУ ДЕРЕВА ПРИПИСЫВАЮТСЯ ВЕСА $w_1$,~\dots, $w_n$ 
(СООТВЕТСТВУЮЩИЕ ДЛИНАМ НАЧАЛЬНЫХ ОТРЕЗКОВ), А СУММЫ СТЕПЕНЕЙ И ДЛИНЫ 
ПУТЕЙ УМНОЖАЮТСЯ НА СООТВЕТСТВУЮЩИЕ ВЕСА. нАПРИМЕР, ЕСЛИ $\cJ$---ДЕРЕВО, 
ПРЕДСТАВЛЕННОЕ НА РИС.~92, ТО 
ПОЛУЧИМ $D(\cJ)=6w_1+6w_2+7w_3+9w_4+9w_5+7w_6+4w_7+4w_8$, 
$E (\cJ)=2w_1+2w_2+2w_3+3w_4+3w_5+2w_6+w_7+w_8$.

дОКАЖИТЕ, ЧТО ПРИ НЕКОТОРОМ $k$ ВСЕГДА СУЩЕСТВУЕТ ОПТИМАЛЬНАЯ СХЕМА, В 
КОТОРОЙ ПЕРВЫМИ СЛИВАЮТСЯ $k$ \emph{САМЫХ КОРОТКИХ ОТРЕЗКОВ}.

%%449

\ex[49] сУЩЕСТВУЕТ, ЛИ АЛГОРИТМ, КОТОРЫЙ ПРИ ЗАДАННЫХ $\alpha$, $\beta$ И 
ВЕСАХ~$w_1$,~\dots, $w_n$ НАХОДИТ ОПТИМАЛЬНЫЕ В СМЫСЛЕ УПР.~7 ДЕРЕВЬЯ, 
ЗАТРАЧИВАЯ ТОЛЬКО $O(n^c)$~ШАГОВ ПРИ НЕКОТОРОМ~$c$?

\ex[M49] (шЛЮМБЕРГЕР И вИЙЕМАН.) вЕРНО ЛИ, ЧТО ДЛЯ ВСЕХ $n$, $\alpha$ И~$\beta$
СУЩЕСТВУЮТ ОПТИМАЛЬНЫЕ В СМЫСЛЕ ТЕОРЕМЫ~H ДЕРЕВЬЯ С $n$~ЛИСТЬЯМИ, У 
КОТОРЫХ ВСЕ ЛИСТЬЯ НАХОДЯТСЯ САМОЕ БОЛЬШЕЕ НА ДВУХ СОСЕДНИХ УРОВНЯХ? 
еСЛИ $\alpha$ И~$\beta$ ФИКСИРОВАНЫ, СУЩЕСТВУЕТ ЛИ ЧИСЛО $m$, ТАКОЕ, ЧТО 
ДЛЯ ВСЕХ ДОСТАТОЧНО БОЛЬШИХ $n$ ИМЕЕТ МЕСТО $A_1(n)=\alpha mn+\beta 
n+A_m(n)$? (оБА ЭТИ ПРЕДПОЛОЖЕНИЯ БЫЛИ ПРОВЕРЕНЫ В СЛУЧАЕ~$\alpha/\beta\ge 4$.)

\ex[вм49] кАКОВО АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ $A_1(n)$ ПРИ $n\to\infty$ 
ПРИ ЗАДАННЫХ $\alpha$ И~$\beta$?

\ex[м29] в ОБОЗНАЧЕНИЯХ (11) И~(16) ДОКАЖИТЕ, ЧТО $f_m(n) + mn\ge 
f(n)$ ПРИ ВСЕХ $m$, $n\ge 2$, И ОПРЕДЕЛИТЕ ВСЕ ТИП, ПРИ КОТОРЫХ ИМЕЕТ 
МЕСТО РАВЕНСТВО.

\ex[25] дОКАЖИТЕ, ЧТО ПРИ ВСЕХ $n>0$ СУЩЕСТВУЕТ ДЕРЕВО С $n$~ЛИСТЬЯМИ И 
МИНИМАЛЬНОЙ ДЛИНОЙ СТЕПЕННОГО ПУТИ (11), ВСЕ ЛИСТЬЯ КОТОРОГО РАСПОЛОЖЕНЫ 
НА ОДНОМ УРОВНЕ.

\ex[M24] пОКАЖИТЕ, ЧТО ПРИ $2\le n \le d(\alpha,\beta)$ ЕДИНСТВЕННОЙ 
НАИЛУЧШЕЙ СХЕМОЙ СЛИЯНИЯ В СМЫСЛЕ ТЕОРЕМЫ~H ЯВЛЯЕТСЯ $n\hbox{-ПУТЕВОЕ}$ 
СЛИЯНИЕ. 
(сР. С ФОРМУЛОЙ (17).)

\ex[40] пРИ ИСПОЛЬЗОВАНИИ КВАДРАТИЧНОГО МЕТОДА РАСПРЕДЕЛЕНИЯ БУФЕРОВ ВРЕМЯ 
ПОИСКА ДЛЯ -СХЕМЫ СЛИЯНИЯ НА РИС.~92 БУДЕТ ПРОПОРЦИОНАЛЬНО
$(\sqrt{2}+\sqrt{4}+\sqrt{1}+\sqrt{1}+\sqrt{8})^2
+(\sqrt{1}+\sqrt{1}+\sqrt{2})^2+\sqrt{1}+\sqrt{2}
+(\sqrt{1}+\sqrt{4})^2+(\sqrt{1}+\sqrt{1}+\sqrt{2})^2$; 
ЭТО ЗНАЧЕНИЕ ПРЕДСТАВЛЯЕТ СОБОЙ СУММУ
ВЕЛИЧИН $(\sqrt{n_1}+\cdots+\sqrt{n_m}+\sqrt{n_1+\cdots+n_m})^2$ ПО ВСЕМ 
ВНУТРЕННИМ УЗЛАМ, ГДЕ ПОДДЕРЕВЬЯ ЭТИХ УЗЛОВ ИМЕЮТ 
$(n_1, \ldots, n_m)$~ЛИСТЬЕВ. 
нАПИШИТЕ ПРОГРАММУ ДЛЯ эвм, КОТОРАЯ ПОРОЖДАЕТ ДЕРЕВЬЯ С 
МИНИМАЛЬНЫМ ВРЕМЕНЕМ ПОИСКА, ИМЕЮЩИЕ $1$, $2$, $3$, \dots{} ЛИСТЬЕВ, 
ИСПОЛЬЗУЯ ДЛЯ ОЦЕНКИ ВРЕМЕНИ ПОИСКА ЭТУ ФОРМУЛУ.

\ex[M22] пОКАЖИТЕ, ЧТО МОЖНО НЕСКОЛЬКО УСИЛИТЬ ТЕОРЕМУ~F, ЕСЛИ 
ЛИФТ ПЕРВОНАЧАЛЬНО ПУСТ И ЕСЛИ $nF(c)\ne t$: В ЭТОМ СЛУЧАЕ НЕОБХОДИМО НЕ 
МЕНЕЕ $\ceil{(nF(c)+b-t)/(b+c)}$~ОСТАНОВОК.

\ex[23] (р.~у.~фЛОЙД.) нАЙДИТЕ ГРАФИК РАБОТЫ ЛИФТА, ПЕРЕВОЗЯЩИЙ ВСЕХ ЛЮДЕЙ 
ИЗ~(22) К ИХ МЕСТАМ НАЗНАЧЕНИЯ ЗА~12 ИЛИ МЕНЬШЕЕ ЧИСЛО ОСТАНОВОК. (в~(23) 
ПОКАЗАНО ПОЛОЖЕНИЕ ПОСЛЕ ОДНОЙ, А НЕ ПОСЛЕ ДВУХ ОСТАНОВОК.)

\ex[25] (б.~т.~бЕННЕТ И а.~ч.~мАК-кЕЛЛАР, 1971.) рАССМОТРИМ СЛЕДУЮЩИЙ 
МЕТОД С СОРТИРОВКОЙ КЛЮЧЕЙ, ПРОДЕМОНСТРИРОВАННЫЙ НА ПРИМЕРЕ ФАЙЛА С 10 КЛЮЧАМИ:
\medskip
\item{a)} иСХОДНЫЙ ФАЙЛ: $(50, I_0)$ $(08, I_1)$ $(51, I_2)$ $(06, I_3)$ $(90, I_4)$ $(17, I_5)$ $(89, I_6)$ $(27, I_7)$ $(65, I_8)$ $(42, I_9)$.

\item{b)} фАЙЛ КЛЮЧЕЙ: $(50, 0)$ $(08, 1)$ $(51, 2)$ $(06, 3)$ $(90, 4)$ $(17, 5)$ $(89, 6)$ $(27, 7)$ $(65, 8)$ $(42, 9)$.

\item{c)} оТСОРТИРОВАННЫЙ (b): $(06, 3)$ $(08, 1)$ $(17, 5)$ $(27, 7)$ $(42, 9)$ $(50,0)$ $(51,2)$ $(65, 8)$ $(89, 6)$ $(90, 4)$.

\item{d)} пРИСВАИВАНИЕ НОМЕРОВ ЯЩИКОВ: $(3, 3)$ $(3, 9)$ $(2, 1)$ $(2, 5)$ $(2, 7)$ $(2, 8)$ $(1, 0)$ $(1, 2)$ $(1, 4)$ $(1, 6)$.

\item{e)} оТСОРТИРОВАННЫЙ (d): $(1, 0)$ $(2, 1)$ $(1, 2)$ $(3, 3)$ $(1, 4)$ $(2, 5)$ $(1, 6)$ $(2, 7)$ $(2, 8)$ $(3, 9)$.

\item{f)} (a), РАСПРЕДЕЛЕННЫЙ ПО ЯЩИКАМ С ИСПОЛЬЗОВАНИЕМ (e):
\itemitem{яЩИК 1:} $(50, I_0)$ $(51, I_2)$ $(90, I_4)$ $(89, I_6)$.
\itemitem{яЩИК 2:} $(08, I_1)$ $(17, I_5)$ $(27, I_7)$ $(65, I_8)$.
\itemitem{яЩИК 3:} $(06, I_3)$ $(42, I_9)$.
\item{g)} рЕЗУЛЬТАТ ВЫБОРА С ЗАМЕЩЕНИЕМ (СНАЧАЛА ЧИТАЕТСЯ ЯЩИК~3, 
ЗАТЕМ ЯЩИК~2, ЗАТЕМ ЯЩИК~1): $(06, I_3)$ $(08, I_1)$ $(17, I_5)$ $(27, I_7)$ $(42, I_9)$ $(50, I_0)$ $(51, I_2)$ $(65, I_8)$ $(89, I_6)$ $(90, I_4)$.
\medskip
\noindent нОМЕРА ЯЩИКОВ НА ШАГЕ~(d) ПРИСВАИВАЮТСЯ ПУТЕМ ПРИМЕНЕНИЯ К~(С) 
\emph{ВЫБОРА С ЗАМЕЩЕНИЕМ СПРАВА НАЛЕВО В УБЫВАЮЩЕМ} ПОРЯДКЕ ПО ВТОРОЙ КОМПОНЕНТЕ.
%%450
нОМЕР ЯЩИКА---ЭТО НОМЕР ОТРЕЗКА. в ПРИВЕДЕННОМ ПРИМЕРЕ ИСПОЛЬЗУЕТСЯ ВЫБОР С 
ЗАМЕЩЕНИЕМ ТОЛЬКО С ДВУМЯ ЭЛЕМЕНТАМИ В ДЕРЕВЕ; ДЛЯ ВЫБОРА С ЗАМЕЩЕНИЕМ 
В~(d) И~(g) ДОЛЖЕН ИСПОЛЬЗОВАТЬСЯ ОДИНАКОВЫЙ РАЗМЕР ДЕРЕВА ВЫБОРА. зАМЕТИМ,
 ЧТО СОДЕРЖИМОЕ ЯЩИКОВ НЕ ОБЯЗАТЕЛЬНО УПОРЯДОЧЕНО.

дОКАЖИТЕ, ЧТО ЭТОТ МЕТОД БУДЕТ СОРТИРОВАТЬ, Т. Е. ЧТО ВЫБОР С ЗАМЕЩЕНИЕМ 
В (g) ОБРАЗУЕТ ЛИШЬ ОДИН ОТРЕЗОК. (эТОТ МЕТОД УМЕНЬШАЕТ ЧИСЛО ЯЩИКОВ, 
ТРЕБУЕМОЕ ОБЫЧНОЙ СОРТИРОВКОЙ КЛЮЧЕЙ ПОСРЕДСТВОМ РАСПРЕДЕЛЕНИЯ, ОСОБЕННО 
ЕСЛИ ИСХОДНЫЕ ДАННЫЕ УЖЕ В СИЛЬНОЙ СТЕПЕНИ УПОРЯДОЧЕНЫ.)

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

мОЖЕТ ПОКАЗАТЬСЯ, ЧТО ПОЯВЛЕНИЕ ВИРТУАЛЬНОЙ ПАМЯТИ ПРИВОДИТ К ОТМИРАНИЮ 
МЕТОДОВ ВНЕШНЕЙ СОРТИРОВКИ, ТАК КАК ЭТА РАБОТА МОЖЕТ БЫТЬ ВЫПОЛНЕНА 
ПРОСТО С ПОМОЩЬЮ МЕТОДОВ, РАЗРАБОТАННЫХ ДЛЯ ВНУТРЕННЕЙ 
СОРТИРОВКИ. рАЗБЕРИТЕ ЭТУ СИТУАЦИЮ. пОЧЕМУ СПЕЦИАЛЬНО РАЗРАБОТАННЫЙ МЕТОД 
ВНЕШНЕЙ СОРТИРОВКИ МОЖЕТ ОКАЗАТЬСЯ ЛУЧШЕ ПРИМЕНЕНИЯ ОБЩЕЙ ТЕХНИКИ 
ПОДКАЧКИ СТРАНИЦ К МЕТОДУ ВНУТРЕННЕЙ СОРТИРОВКИ?


\subchap{резюме. история и библиография} % 5.5
тЕПЕРЬ, КОГДА МЫ ПОЧТИ ДОСТИГЛИ КОНЦА ЭТОЙ ОЧЕНЬ ДЛИННОЙ ГЛАВЫ, СТОИТ 
"ОТСОРТИРОВАТЬ" НАИБОЛЕЕ ВАЖНЫЕ ФАКТЫ ИЗ ЧИСЛА ИЗУЧЕННЫХ.

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

\emph{вНУТРЕННЯЯ СОРТИРОВКА} ИСПОЛЬЗУЕТСЯ В ТЕХ СЛУЧАЯХ, КОГДА ВСЕ ЗАПИСИ 
ПОМЕЩАЮТСЯ В БЫСТРОЙ ВНУТРЕННЕЙ ПАМЯТИ МАШИНЫ. мЫ ИЗУЧИЛИ С РАЗНОЙ 
СТЕПЕНЬЮ ДЕТАЛИЗАЦИИ БОЛЕЕ ДВУХ ДЕСЯТКОВ АЛГОРИТМОВ ВНУТРЕННЕЙ СОРТИРОВКИ, 
НО НАМ, НАВЕРНОЕ, БЫЛО БЫ КУДА СПОКОЙНЕЕ, ЕСЛИ БЫ МЫ НЕ ЗНАЛИ ТАК МНОГО 
РАЗЛИЧНЫХ ПОДХОДОВ К ЭТОЙ ЗАДАЧЕ! иЗУЧЕНИЕ ВСЕХ ЭТИХ МЕТОДОВ БЫЛО ПРИЯТНЫМ 
ВРЕМЯПРОВОЖДЕНИЕМ. нО ТЕПЕРЬ ПЕРЕД НАМИ БЕЗРАДОСТНАЯ 
ПЕРСПЕКТИВА---ПРЕДСТОИТ НА ДЕЛЕ РЕШИТЬ, КАКОЙ МЕТОД СЛЕДУЕТ ИСПОЛЬЗОВАТЬ В 
ТОЙ ИЛИ ИНОЙ КОНКРЕТНОЙ СИТУАЦИИ.

бЫЛО БЫ ПРЕКРАСНО, ЕСЛИ БЫ ТОЛЬКО ОДИН ИЛИ ДВА МЕТОДА СОРТИРОВКИ 
ПРЕВОСХОДИЛИ ВСЕ ОСТАЛЬНЫЕ БЕЗОТНОСИТЕЛЬНО К ПРИЛОЖЕНИЮ ИЛИ ИСПОЛЬЗУЕМОЙ 
МАШИНЕ. нА САМОМ ЖЕ ДЕЛЕ КАЖДЫЙ МЕТОД ИМЕЕТ СВОИ СОБСТВЕННЫЕ, ОДНОМУ ЕМУ 
ПРИСУЩИЕ ДОСТОИНСТВА. нАПРИМЕР, МЕТОД ПУЗЫРЬКА (АЛГОРИТМ~5.2.2в) НЕ ИМЕЕТ 
ЯРКО ВЫРАЖЕННЫХ ПРЕИМУЩЕСТВ, ТАК КАК ВСЕГДА МОЖНО НАЙТИ ЛУЧШИЙ СПОСОБ 
СДЕЛАТЬ ТО, ЧТО ОН ДЕЛАЕТ; НО ДАЖЕ ЭТОТ МЕТОД ПОСЛЕ СООТВЕТСТВУЮЩЕГО 
ОБОБЩЕНИЯ ОКАЗЫВАЕТСЯ ПОЛЕЗНЫМ ДЛЯ СОРТИРОВКИ С ДВУМЯ ЛЕНТАМИ (СМ. 
П.~5.4.8). иТАК, ПРИХОДИМ К ЗАКЛЮЧЕНИЮ, ЧТО ПОЧТИ ВСЕ АЛГОРИТМЫ 
ЗАСЛУЖИВАЮТ ТОГО, ЧТОБЫ О НИХ ПОМНИЛИ, ТАК КАК СУЩЕСТВУЮТ ПРИЛОЖЕНИЯ, В 
КОТОРЫХ ОНИ ОКАЗЫВАЮТСЯ ВЕСЬМА ХОРОШИМИ.

в СЛЕДУЮЩЕМ КРАТКОМ ОБЗОРЕ ОСВЕЩАЮТСЯ ОСНОВНЫЕ АСПЕКТЫ НАИБОЛЕЕ ВАЖНЫХ 
АЛГОРИТМОВ ВНУТРЕННЕЙ СОРТИРОВКИ, С КОТОРЫМИ МЫ ВСТРЕЧАЛИСЬ. (кАК ОБЫЧНО,
 $N$ ОЗНАЧАЕТ ЧИСЛО ЗАПИСЕЙ В ФАЙЛЕ.)

%%452

1. {\sl рАСПРЕДЕЛЯЮЩИЙ ПОДСЧЕТ.\/} аЛГОРИТМ~5.2D ОЧЕНЬ ПОЛЕЗЕН, ЕСЛИ 
ДИАПАЗОН КЛЮЧЕЙ НЕВЕЛИК. мЕТОД УСТОЙЧИВ (НЕ ИЗМЕНЯЕТСЯ ПОРЯДОК ЗАПИСЕЙ С 
РАВНЫМИ КЛЮЧАМИ), НО ТРЕБУЕТСЯ ПАМЯТЬ ДЛЯ СЧЕТЧИКОВ И $2N$~ЗАПИСЕЙ. оДНА 
ИЗ МОДИФИКАЦИЙ, ЭКОНОМЯЩАЯ $N$ ИЗ ЭТИХ ЗАПИСЕЙ ЦЕНОЙ УСТОЙЧИВОСТИ, 
ВСТРЕЧАЕТСЯ В УПР. 5.2-13.

2. {\sl пРОСТЫЕ ВСТАВКИ.\/} аЛГОРИТМ 5.2.1S НАИБОЛЕЕ ПРОСТ 
ДЛЯ ПРОГРАММИРОВАНИЯ, НЕ ТРЕБУЕТ ДОПОЛНИТЕЛЬНОГО ПРОСТРАНСТВА И ВПОЛНЕ 
ЭФФЕКТИВЕН ПРИ МАЛЫХ~$N$ (СКАЖЕМ, ПРИ $N\le 25$). пРИ БОЛЬШИХ~$N$ ОН 
СТАНОВИТСЯ НЕВЫНОСИМО МЕДЛЕННЫМ, ЕСЛИ ТОЛЬКО ИСХОДНЫЕ ДАННЫЕ НЕ ОКАЖУТСЯ 
СРАЗУ ПОЧТИ УПОРЯДОЧЕННЫМИ.

3. {\sl сОРТИРОВКА С УБЫВАЮЩИМ ШАГОМ.\/} аЛГОРИТМ 5.2.1D (МЕТОД шЕЛЛА) ТАК 
ЖЕ ДОВОЛЬНО ПРОСТО ПРОГРАММИРУЕТСЯ, ИСПОЛЬЗУЕТ МИНИМАЛЬНЫЙ ОБRЕМ ПАМЯТИ И 
ДОВОЛЬНО ЭФФЕКТИВЕН ПРИ УМЕРЕННО БОЛЬШИХ~$N$ (СКАЖЕМ, ПРИ $N\le 1000$).

4. {\sl вСТАВКИ В СПИСОК.\/} аЛГОРИТМ 5.2.1L ОСНОВАН НА ТОЙ ЖЕ ИДЕЕ, ЧТО И 
ПРОСТЫЕ ВСТАВКИ, И ПОЭТОМУ ГОДИТСЯ ТОЛЬКО ПРИ НЕБОЛЬШИХ~$N$. кАК И В 
ДРУГИХ МЕТОДАХ СОРТИРОВКИ СПИСКОВ, В НЕМ БЛАГОДАРЯ ОПЕРАЦИЯМ СО ССЫЛКАМИ 
ЭКОНОМИТСЯ СТОИМОСТЬ ПЕРЕМЕЩЕНИЯ ДЛИННЫХ ЗАПИСЕЙ; ЭТО ОСОБЕННО УДОБНО, 
КОГДА ЗАПИСИ ИМЕЮТ ПЕРЕМЕННУЮ ДЛИНУ ИЛИ ЯВЛЯЮТСЯ ЧАСТЬЮ ДРУГИХ СТРУКТУР ДАННЫХ.

5. {\sl сОРТИРОВКА С ВЫЧИСЛЕНИЕМ АДРЕСА\/} ЭФФЕКТИВНА, ЕСЛИ КЛЮЧИ 
 ПОДЧИНЯЮТСЯ ИЗВЕСТНОМУ (ОБЫЧНО РАВНОМЕРНОМУ) ЗАКОНУ РАСПРЕДЕЛЕНИЯ; 
ВАЖНЕЙШИМИ ВАРИАНТАМИ ЭТОГО ПОДХОДА ЯВЛЯЮТСЯ \emph{ВСТАВКИ В НЕСКОЛЬКО СПИСКОВ}
(АЛГОРИТМ 5.2.1м) И КОМБИНИРОВАННАЯ ПОРАЗРЯДНАЯ СОРТИРОВКА СО 
ВСТАВКАМИ мАКЛАРЕНА (РАССМОТРЕННАЯ В КОНЦЕ П.~5.2.5). дЛЯ ПОСЛЕДНЕГО 
МЕТОДА ДОСТАТОЧНО ИМЕТЬ $O(\sqrt{N})$ ДОПОЛНИТЕЛЬНЫХ ЯЧЕЕК ПАМЯТИ.

6. {\sl оБМЕННАЯ СОРТИРОВКА СО СЛИЯНИЕМ.\/} аЛГОРИТМ 5.2.2м (МЕТОД 
бЭТЧЕРА) И РОДСТВЕННЫЙ ЕМУ АЛГОРИТМ \emph{БИТОННОЙ 
СОРТИРОВКИ} (УПР.~5.3.4-10) ПОЛЕЗНЫ, ЕСЛИ МОЖНО ОДНОВРЕМЕННО 
ВЫПОЛНЯТЬ БОЛЬШОЕ ЧИСЛО СРАВНЕНИЙ.

7. {\sl оБМЕННАЯ СОРТИРОВКА С РАЗДЕЛЕНИЕМ\/} (МЕТОД хОАРА, 
ШИРОКО ИЗВЕСТНЫЙ КАК \emph{БЫСТРАЯ СОРТИРОВКА}). аЛГОРИТМ 5.2.2Q, ВЕРОЯТНО,
 САМЫЙ ПОЛЕЗНЫЙ УНИВЕРСАЛЬНЫЙ АЛГОРИТМ ВНУТРЕННЕЙ СОРТИРОВКИ, ПОСКОЛЬКУ 
ОН ТРЕБУЕТ ОЧЕНЬ МАЛО ПАМЯТИ И ОПЕРЕЖАЕТ СВОИХ КОНКУРЕНТОВ ПО СРЕДНЕМУ 
ВРЕМЕНИ ВЫПОЛНЕНИЯ НА БОЛЬШИНСТВЕ ВЫЧИСЛИТЕЛЬНЫХ МАШИН. оДНАКО В 
НАИХУДШЕМ СЛУЧАЕ ОН МОЖЕТ РАБОТАТЬ ОЧЕНЬ МЕДЛЕННО. пОЭТОМУ, ЕСЛИ 
ВЕРОЯТНОСТЬ НЕСЛУЧАЙНЫХ ДАННЫХ ДОСТАТОЧНО ВЕЛИКА, ПРИХОДИТСЯ 
ТЩАТЕЛЬНО ВЫБИРАТЬ РАЗДЕЛЯЮЩИЙ ЭЛЕМЕНТ. еСЛИ ВЫБИРАЕТСЯ МЕДИАНА ИЗ ТРЕХ 
ЭЛЕМЕНТОВ (КАК ПРЕДЛАГАЕТСЯ В УПР. 5.2.2-55), ТО ТАКОЕ
%%453
ПОВЕДЕНИЕ, КАК В НАИХУДШЕМ СЛУЧАЕ, СТАНОВИТСЯ КРАЙНЕ МАЛОВЕРОЯТНЫМ И, 
КРОМЕ ТОГО, НЕСКОЛЬКО УМЕНЬШАЕТСЯ СРЕДНЕЕ ВРЕМЯ РАБОТЫ.

8.~{\sl пРОСТОЙ ВЫБОР.\/} аЛГОРИТМ~5.2.3S ДОВОЛЬНО ПРОСТ И ОСОБЕННО 
ПОДХОДИТ В СЛУЧАЕ, КОГДА ИМЕЕТСЯ СПЕЦИАЛЬНОЕ ОБОРУДОВАНИЕ ДЛЯ БЫСТРОГО 
ПОИСКА НАИМЕНЬШЕГО ЭЛЕМЕНТА В СПИСКЕ.

9.~{\sl пИРАМИДАЛЬНАЯ СОРТИРОВКА.\/} аЛГОРИТМ~5.2.4н ПРИ МИНИМАЛЬНЫХ 
ТРЕБОВАНИЯХ ПАМЯТИ ОБЕСПЕЧИВАЕТ ДОСТАТОЧНО ВЫСОКУЮ СКОРОСТЬ СОРТИРОВКИ; 
КАК СРЕДНЕЕ ВРЕМЯ РАБОТЫ, ТАК И МАКСИМАЛЬНОЕ ВРЕМЯ ПРИМЕРНО ВДВОЕ БОЛЬШЕ 
СРЕДНЕГО ВРЕМЕНИ БЫСТРОЙ СОРТИРОВКИ.

10.~{\sl  сЛИЯНИЕ СПИСКОВ.\/} аЛГОРИТМ~5.2.4L ОСУЩЕСТВЛЯЕТ СОРТИРОВКУ 
СПИСКОВ, ПРИ КОТОРОЙ, ТАК ЖЕ КАК И ПРИ ПИРАМИДАЛЬНОЙ СОРТИРОВКЕ, 
ОБЕСПЕЧИВАЕТСЯ ВЕСЬМА ВЫСОКАЯ СКОРОСТЬ ДАЖЕ В НАИХУДШЕМ СЛУЧАЕ, КРОМЕ 
ТОГО, ЭТОТ МЕТОД УСТОЙЧИВ ПО ОТНОШЕНИЮ К РАВНЫМ КЛЮЧАМ.

11.~{\sl  пОРАЗРЯДНАЯ СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ АЛГОРИТМА\/} 5.2.5R---ЭТО 
НЕ ЧТО ИНОЕ, КАК СОРТИРОВКА СПИСКОВ, КОТОРАЯ ПРИЕМЛЕМА ДЛЯ КЛЮЧЕЙ, ЛИБО 
ОЧЕНЬ КОРОТКИХ, ЛИБО ИМЕЮЩИХ НЕОБЫЧНЫЙ ПОРЯДОК ЛЕКСИКОГРАФИЧЕСКОГО 
СРАВНЕНИЯ. вМЕСТО ССЫЛОК МОЖНО ПРИМЕНИТЬ РАСПРЕДЕЛЯЮЩИЙ ПОДСЧЕТ 
(ПУНКТ~1 НАШЕГО ОБЗОРА); ТАКАЯ ПРОЦЕДУРА ПОТРЕБУЕТ ПРОСТРАНСТВА ДЛЯ 
$2N$~ЗАПИСЕЙ И ДЛЯ ТАБЛИЦЫ, СЧЕТЧИКОВ, НО БЛАГОДАРЯ ПРОСТОТЕ ВНУТРЕННЕГО 
ЦИКЛА ОНА ОСОБЕННО ХОРОША ДЛЯ СВЕРХБЫСТРЫХ эвм---"ПОЖИРАТЕЛЬНИЦ ЧИСЕЛ", 
ИМЕЮЩИХ ОПЕРЕЖАЮЩЕЕ УПРАВЛЕНИЕ. (\emph{пРЕДОСТЕРЕЖЕНИЕ.} пОРАЗРЯДНУЮ 
СОРТИРОВКУ НЕ СЛЕДУЕТ ИСПОЛЬЗОВАТЬ ПРИ МАЛЫХ~$N$.)

12.~{\sl  сОРТИРОВКА ВСТАВКАМИ И СЛИЯНИЕМ\/} (СМ.~П.~5.3.1) 
НАИБОЛЕЕ ПРИЕМЛЕМА ПРИ ОЧЕНЬ МАЛЫХ~$N$ В "ПРЯМОЛИНЕЙНЫХ" 
ПРОГРАММАХ. нАПРИМЕР, ЭТОТ МЕТОД ОКАЗАЛСЯ БЫ ПОДХОДЯЩИМ В ТЕХ 
ПРИЛОЖЕНИЯХ, ГДЕ ТРЕБУЕТСЯ СОРТИРОВАТЬ МНОГО ГРУПП ИЗ ПЯТИ ИЛИ 
ШЕСТИ ЗАПИСЕЙ.

13.  мОГУТ СУЩЕСТВОВАТЬ И ГИБРИДНЫЕ МЕТОДЫ, ОБRЕДИНЯЮЩИЕ ОДИН ИЛИ БОЛЕЕ ИЗ 
ПРИВЕДЕННЫХ ВЫШЕ МЕТОДОВ. нАПРИМЕР, КОРОТКИЕ ПОДФАЙЛЫ, ВОЗНИКАЮЩИЕ ПРИ 
БЫСТРОЙ СОРТИРОВКЕ, МОЖНО СОРТИРОВАТЬ СЛИЯНИЕМ И ВСТАВКАМИ.

14. и НАКОНЕЦ, ДЛЯ РЕАЛИЗАЦИИ БЕЗЫМЯННОГО МЕТОДА, ВСТРЕТИВШЕГОСЯ В 
ОТВЕТЕ К УПР.~5.2.1-3, ТРЕБУЕТСЯ, ПО-ВИДИМОМУ, КРАТЧАЙШАЯ ИЗ ВОЗМОЖНЫХ 
ПРОГРАММ СОРТИРОВКИ. нО СРЕДНЕЕ ВРЕМЯ РАБОТЫ ТАКОЙ ПРОГРАММЫ 
ПРОПОРЦИОНАЛЬНО~$N^3$, Т.~Е.~ЭТО САМАЯ МЕДЛЕННАЯ ПРОГРАММА СОРТИРОВКИ В КНИГЕ!

пРОСТРАНСТВЕННЫЕ И ВРЕМЕННЫЕ ХАРАКТЕРИСТИКИ МНОГИХ ИЗ ЭТИХ МЕТОДОВ, 
ЗАПРОГРАММИРОВАННЫХ ДЛЯ \MIX, СВЕДЕНЫ В ТАБЛ.~1.
%%454
\picture{тАБЛИЦА 1, СТР. 454}
вАЖНО ИМЕТЬ В ВИДУ, ЧТО ЧИСЛА В ЭТОЙ ТАБЛИЦЕ ЯВЛЯЮТСЯ ЛИШЬ ГРУБЫМИ 
ПОКАЗАТЕЛЯМИ ОТНОСИТЕЛЬНОГО ВРЕМЕНИ СОРТИРОВКИ. оНИ ПРИМЕНИМЫ ТОЛЬКО К 
ОДНОЙ эвм, И ПРЕДПОЛОЖЕНИЯ, КАСАЮЩИЕСЯ ИСХОДНЫХ ДАННЫХ, ДАЛЕКО НЕ ДЛЯ ВСЕХ 
ПРОГРАММ АБСОЛЮТНО ПРАВОМЕРНЫ. сРАВНИТЕЛЬНЫЕ ТАБЛИЦЫ, ПОДОБНЫЕ ЭТОЙ, 
ПРИВОДИЛИСЬ ВО МНОГИХ РАБОТАХ, НО НЕ НАЙДЕТСЯ ТАКИХ ДВУХ АВТОРОВ,
 КОТОРЫЕ ПРИШЛИ БЫ К ОДИНАКОВЫМ ВЫВОДАМ! тЕМ НЕ МЕНЕЕ УКАЗАНИЯ О ВРЕМЕНИ 
РАБОТЫ ПОЗВОЛЯЮТ ОЦЕНИТЬ ХОТЯ БЫ ПОРЯДОК СКОРОСТИ, КОТОРУЮ СЛЕДУЕТ ОЖИДАТЬ 
ОТ КАЖДОГО АЛГОРИТМА ПРИ СОРТИРОВКЕ ЗАПИСЕЙ ИЗ ОДНОГО СЛОВА, ТАК КАК 
\MIX---ДОВОЛЬНО ТИПИЧНАЯ МАШИНА.

сТОЛБЕЦ "ПРОСТРАНСТВО" В ТАБЛ.~1 СОДЕРЖИТ НЕКОТОРУЮ ИНФОРМАЦИЮ О 
КОЛИЧЕСТВЕ ВСПОМОГАТЕЛЬНОЙ ПАМЯТИ, ИСПОЛЬЗУЕМОЙ КАЖДЫМ АЛГОРИТМОМ, В 
ЕДИНИЦАХ ДЛИНЫ ЗАПИСИ. зДЕСЬ БУКВОЙ~$\varepsilon$ ОБОЗНАЧЕНА ДОЛЯ ЗАПИСИ, 
ТРЕБУЕМАЯ ДЛЯ ОДНОГО ПОЛЯ СВЯЗИ; ТАК, НАПРИМЕР, $N(1+\varepsilon)$ 
ОЗНАЧАЕТ, ЧТО МЕТОД ТРЕБУЕТ ПРОСТРАНСТВО ДЛЯ $N$~ЗАПИСЕЙ И $N$~ПОЛЕЙ СВЯЗИ.

в АСИМПТОТИЧЕСКИХ СРЕДНИХ И МАКСИМАЛЬНЫХ ВРЕМЕНАХ, СОДЕРЖАЩИХСЯ В 
ТАБЛ.~1, УЧИТЫВАЮТСЯ ТОЛЬКО ГЛАВНЫЕ ЧЛЕНЫ, ДОМИНИРУЮЩИЕ ПРИ БОЛЬШИХ~$N$ В 
ПРЕДПОЛОЖЕНИИ СЛУЧАЙНЫХ ИСХОДНЫХ ДАННЫХ; $c$~ОБОЗНАЧАЕТ ПРОИЗВОЛЬНУЮ 
КОНСТАНТУ. эТИ ФОРМУЛЫ МОГУТ ИНОГДА ВВЕСТИ В ЗАБЛУЖДЕНИЕ, ПОЭТОМУ 
УКАЗАНО ТАКЖЕ ФАКТИЧЕСКОЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ ДЛЯ ДВУХ КОНКРЕТНЫХ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИСХОДНЫХ ДАННЫХ. сЛУЧАЙ $N=16$, ОТНОСИТСЯ К 
ШЕСТНАДЦАТИ КЛЮЧАМ, ТАК ЧАСТО ПОЯВЛЯВШИМСЯ В ПРИМЕРАХ \S~5.2, А СЛУЧАЙ 
$N=1000$ ОТНОСИТСЯ К ПОСЛЕДОВАТЕЛЬНОСТИ $K_1$, $K_2$,~\dots, $K_{1000}$, 
ОПРЕДЕЛЕННОЙ ФОРМУЛАМИ
$$
K_0=0; \quad K_{n+1}=(3141592621K_n+2113148651)\bmod 10^{10}.
$$
дЛЯ ПОЛУЧЕНИЯ ХАРАКТЕРИСТИК КАЖДОГО АЛГОРИТМА, ПРЕДСТАВЛЕННОГО В ТАБЛИЦЕ,
 ИСПОЛЬЗОВАЛАСЬ ВПОЛНЕ "ВЫСОКОКАЧЕСТВЕННАЯ" \MIX-ПРОГРАММА, ЧАСТО С УЧЕТОМ 
УСОВЕРШЕНСТВОВАНИЙ, ПРЕДЛОЖЕННЫХ В УПРАЖНЕНИЯХ. рАЗМЕР БАЙТА ПРИ 
ВЫПОЛНЕНИИ ЭТИХ ПРОГРАММ ПРИНЯТ РАВНЫМ 100.

дЛЯ \emph{ВНЕШНЕЙ СОРТИРОВКИ} НЕОБХОДИМЫ МЕТОДЫ, ОТЛИЧАЮЩИЕСЯ ОТ МЕТОДОВ 
ВНУТРЕННЕЙ СОРТИРОВКИ, ПОТОМУ ЧТО В ЭТОМ СЛУЧАЕ ПРЕДПОЛАГАЕТСЯ 
ИСПОЛЬЗОВАНИЕ СРАВНИТЕЛЬНО ПРОСТЫХ СТРУКТУР ДАННЫХ И БОЛЬШОЕ ВНИМАНИЕ 
УДЕЛЯЕТСЯ УМЕНЬШЕНИЮ ВРЕМЕНИ ВВОДА/ВЫВОДА. в П.~5.4.6 РАССМАТРИВАЮТСЯ 
ИНТЕРЕСНЫЕ МЕТОДЫ, РАЗВИТЫЕ ДЛЯ ЛЕНТОЧНОЙ СОРТИРОВКИ, А В П.~5.4.9 
ОБСУЖДАЕТСЯ ИСПОЛЬЗОВАНИЕ ДИСКОВ И БАРАБАНОВ.

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

\section рАННИЕ РАЗРАБОТКИ. пОИСК ИСТОЧНИКА СОВРЕМЕННЫХ МЕТОДОВ 
СОРТИРОВКИ ВОЗВРАЩАЕТ НАС В 19-Е~СТОЛЕТИЕ, КОГДА БЫЛИ ИЗОБРЕТЕНЫ ПЕРВЫЕ 
МАШИНЫ ДЛЯ СОРТИРОВКИ. в сОЕДИНЕННЫХ шТАТАХ ПЕРЕПИСЬ ВСЕХ ГРАЖДАН 
ПРОВОДИТСЯ КАЖДЫЕ 10~ЛЕТ, И УЖЕ К 1880~Г. ПРОБЛЕМА ОБРАБОТКИ ОГРОМНЫХ ПО 
ОБRЕМУ ДАННЫХ ПЕРЕПИСИ СТАЛА ОЧЕНЬ ОСТРОЙ; И В САМОМ ДЕЛЕ, ЧИСЛО ОДИНОКИХ 
(В ОТЛИЧИЕ ОТ ЧИСЛА СОСТОЯЩИХ В БРАКЕ) В 1880~Г. В ТАБЛИЦАХ ОТСУТСТВУЕТ, ХОТЯ
\picture{рИС. 94. тАБУЛЯТОР хОЛЛЕРИТА. (фОТОГРАФИЯ ЛЮБЕЗНО ПРЕДОСТАВЛЕНА 
АРХИВОМ IBM.)
}
ВСЯ НЕОБХОДИМАЯ, ИНФОРМАЦИЯ БЫЛА СОБРАНА. гЕРМАН хОЛЛЕРИТ, ДВАДЦАТИЛЕТНИЙ 
СЛУЖАЩИЙ бЮРО ПЕРЕПИСИ, ИЗОБРЕЛ ОСТРОУМНЫЙ ЭЛЕКТРИЧЕСКИЙ ТАБУЛЯТОР, 
ОТВЕЧАЮЩИЙ НУЖДАМ СБОРА СТАТИСТИКИ, И ОКОЛО 100 ЕГО МАШИН УСПЕШНО 
ИСПОЛЬЗОВАЛИСЬ ПРИ ОБРАБОТКЕ СПИСКОВ ПЕРЕПИСИ 1890~Г.

нА РИС.~94 ИЗОБРАЖЕН ПЕРВЫЙ АППАРАТ хОЛЛЕРИТА, ПРИВОДИМЫЙ В ДЕЙСТВИЕ ОТ 
АККУМУЛЯТОРНЫХ БАТАРЕЙ. дЛЯ НАС ОСНОВНОЙ ИНТЕРЕС ПРЕДСТАВЛЯЕТ 
"СОРТИРОВАЛЬНЫЙ ЯЩИК" СПРАВА, КОТОРЫЙ ОТКРЫТ С  ЦЕЛЬЮ ПОКАЗАТЬ ПОЛОВИНУ ИЗ 
26 ВНУТРЕННИХ ОТДЕЛЕНИЙ. оПЕРАТОР ВСТАВЛЯЕТ ПЕРФОКАРТУ РАЗМЕРА 
$6{5\over8}\times3{1\over4}$~ДЮЙМОВ В "ПРЕСС" И ОПУСКАЕТ РУКОЯТКУ; ЭТО 
ПРИВОДИТ К ТОМУ, ЧТО ЗАКРЕПЛЕННЫЕ НА ПРУЖИНАХ ШТЫРИ НА ВЕРХНЕЙ ПАНЕЛИ В ТЕХ
%%457
\bye