\input style
ТАБЛИЦЫ ИНВЕРСИЙ ДЛЯ РИС.~14:
$$
\vcenter{\halign{
#\hfil\bskip&&\bskip$#$\bskip\cr
 & 3 & 1 & 8 & 3 & 4 & 5 & 0 & 4 & 0 & 3& 2 & 2 & 3 & 2 & 1 & 0\cr
пРОСМОТР~1\cr
 & 2 & 0 & 7 & 2 & 3 & 4 & 0 & 3 & 0 & 2 & 1 & 1 & 2 & 1 & 0 & 0\cr
пРОСМОТР~2\cr
 & 1 & 0 & 6 & 1 & 2 & 3 & 0 & 2 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0\cr
пРОСМОТР~3\cr
 & 0 & 0 & 5 & 0 & 1 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
}}
\eqno  (1)
$$
И~Т.~Д. пОЭТОМУ, ЕСЛИ~$b_1\,b_2\,\ldots\,b_n$---ТАБЛИЦА ИНВЕРСИЙ 
ИСХОДНОЙ ПЕРЕСТАНОВКИ, ТО ДОЛЖНЫ ВЫПОЛНЯТЬСЯ РАВЕНСТВА
$$
\eqalignno{
A&=1+\max(b_1, b_2,\ldots, b_n); & (2) \cr
B&=b_1+b_2+\cdots+b_n; & (3) \cr
C&=c_1+c_2+\cdots+c_A, & (4) \cr
}
$$
ГДЕ~$c_j$---ЗНАЧЕНИЕ~$|BOUND|-1$ ПЕРЕД НАЧАЛОМ 
$j\hbox{-ГО}$~ПРОСМОТРА. иСПОЛЬЗУЯ ТАБЛИЦЫ ИНВЕРСИЙ, ЗАПИШЕМ
$$
c_j=\max\set{ b_i+i \mid b_i\ge j-1}-j
\eqno(5)
$$
(СМ.~УПР.~5). сЛЕДОВАТЕЛЬНО, В ПРИМЕРЕ~(1) $A=9$, $B=41$, 
$C=15+14+13+12+7+5+4+3+2=75$. оБЩЕЕ ВРЕМЯ СОРТИРОВКИ НА МАШИНЕ \MIX{} ДЛЯ 
РИС.~14 РАВНО~$1030u$.

рАСПРЕДЕЛЕНИЕ ВЕЛИЧИНЫ~$B$ (СУММАРНОЕ ЧИСЛО ИНВЕРСИЙ В СЛУЧАЙНОЙ 
ПЕРЕСТАНОВКЕ) НАМ УЖЕ ХОРОШО ИЗВЕСТНО; ТАКИМ ОБРАЗОМ, ОСТАЕТСЯ 
ПРОАНАЛИЗИРОВАТЬ ВЕЛИЧИНЫ~$A$ И~$C$.

вЕРОЯТНОСТЬ ТОГО, ЧТО~$A\le k$, РАВНА ПРОИЗВЕДЕНИЮ~$1/n!$ НА ЧИСЛО ТАБЛИЦ 
ИНВЕРСИЙ, НЕ СОДЕРЖАЩИХ КОМПОНЕНТ~$\ge k$, ИМЕННО~$k^{n-k}k!$ 
ПРИ~$1\le k \le n$. сЛЕДОВАТЕЛЬНО, ВЕРОЯТНОСТЬ ТОГО, ЧТО ПОТРЕБУЕТСЯ РОВНО 
$k$~ПРОСМОТРОВ, РАВНА
$$
A_k={1\over n!}(k^{n-k}k!-(k-1)^{n-k+1}(k-1)!).
\eqno(6)
$$
тЕПЕРЬ МОЖНО ВЫЧИСЛИТЬ СРЕДНЕЕ ЗНАЧЕНИЕ~$\sum k A_k$, 
ПРОИЗВОДЯ СУММИРОВАНИЕ ПО ЧАСТЯМ, ПОЛУЧАЕМ
$$
A_{ave}=n+1\sum_{0\le k \le n} -{k^{n-k}k!\over n!}=n+1+P(n),
\eqno(7)
$$
ГДЕ~$P(n)$---ФУНКЦИЯ, АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ КОТОРОЙ, КАК БЫЛО ПОКАЗАНО В 
П.~1.2.11, ОПИСЫВАЕТСЯ ФОРМУЛОЙ~$\sqrt{\pi n/2}-{2\over3}+O(1/\sqrt{n})$. 
фОРМУЛА~(7) БЫЛА НАЙДЕНА БЕЗ ДОКАЗАТЕЛЬСТВА
э.~X.~фРЭНДОМ [{\sl JACM,\/} {\bf 3} (1956), 150]; ДОКАЗАТЕЛЬСТВО В 
СВОЕЙ ДОКТОРСКОЙ ДИССЕРТАЦИИ ПРИВЕЛ гОВАРД~б.~дЕМУТ 
[(Stanford University: October, 1956), 64--68]. сТАНДАРТНОЕ 
ОТКЛОНЕНИЕ ВЕЛИЧИНЫ~$A$ СМ.~В~УПР.~7.

%% 135

сУММАРНОЕ ЧИСЛО СРАВНЕНИЙ~$C$ ИССЛЕДОВАТЬ НЕСКОЛЬКО СЛОЖНЕЕ, И МЫ 
РАССМОТРИМ ТОЛЬКО~$C_{ave}$. пУСТЬ~$f_j(k)$---ЧИСЛО ТАКИХ ТАБЛИЦ 
ИНВЕРСИЙ~$b_1\,\ldots\,b_n$ ($n$~ФИКСИРОВАНО), ЧТО ПРИ~$1\le i \le n$ 
ЛИБО~$b_i<j-1$, ЛИБО~$b_i+i-j\le k$; ТОГДА
$$
f_j(k)=(j+k)! (j-1)^{n-j-k} \rem{ПРИ~$0\le k \le n-j$.}
\eqno (8)
$$
(сМ.~УПР.~8.) сРЕДНЕЕ ЗНАЧЕНИЕ~$c_j$ В~(5) РАВНО~$\sum 
k(f_j(k)-f_j(k-1)))/n!$; СУММИРУЯ ПО ЧАСТЯМ, А ЗАТЕМ ПО~$j$, ПОЛУЧАЕМ ФОРМУЛУ
$$
C_{ave}=\perm{n+1}{2}-{1\over n!}
\sum_{\scriptstyle 1\le j \le n \atop \scriptstyle 0\le k \le n-j} f_j(k)=
\perm{n+1}{2}-{1\over n!}\sum_{0\le r < s \le n} s! r^{n-s}.
\eqno(9)
$$
оПРЕДЕЛИТЬ АСИМПТОТИЧЕСКОЕ ЗНАЧЕНИЕ ЗДЕСЬ НЕ ТАК ПРОСТО, И  МЫ ВЕРНЕМСЯ К 
НЕМУ В КОНЦЕ ЭТОГО ПУНКТА.

чТОБЫ ПОДВЕСТИ ИТОГ НАШЕГО АНАЛИЗА МЕТОДА ПУЗЫРЬКА, ЗАПИШЕМ ФОРМУЛЫ, 
ВЫВЕДЕННЫЕ ВЫШЕ (А ТАКЖЕ НИЖЕ), СЛЕДУЮЩИМ ОБРАЗОМ:
$$
\eqalignno{
A&=(\min 1, \ave N-\sqrt{\pi N/2}+O(1), \max N); & (10) \cr
B&=(\min 0, \ave {1\over4}(N^2-N), \max{1\over 2}(N^2-N)); & (11) \cr
C&=\left(\min N-1, \ave{1\over 2}(N^2-N\ln N-(\gamma+\ln 2-1)N)+O(\sqrt{N}),
   \max {1\over 2}(N^2-N)\right). & (12) \cr
}
$$
вО ВСЕХ СЛУЧАЯХ МИНИМУМ ДОСТИГАЕТСЯ, КОГДА ИСХОДНЫЙ ФАЙЛ УЖЕ УПОРЯДОЧЕН, А 
МАКСИМУМ---КОГДА ЗАПИСИ РАСПОЛОЖЕНЫ В ОБРАТНОМ ПОРЯДКЕ; ТАКИМ ОБРАЗОМ, 
ВРЕМЯ РАБОТЫ ДЛЯ МАШИНЫ~\MIX{} 
РАВНО~$8A+7B+8C+1=(\min 8N+1, \ave 5.75N^2+O(N \ln N), \max 7.5N^2+0.5N+1)$.

\section уСОВЕРШЕНСТВОВАНИЯ МЕТОДА ПУЗЫРЬКА. мЫ ПОТРАТИЛИ МНОГО УСИЛИЙ НА 
АНАЛИЗ МЕТОДА ПУЗЫРЬКА, И, ХОТЯ СПОСОБЫ, ПРИМЕНЯВШИЕСЯ ПРИ ВЫЧИСЛЕНИЯХ, 
ПОУЧИТЕЛЬНЫ, РЕЗУЛЬТАТЫ РАЗОЧАРОВЫВАЮТ, ПОСКОЛЬКУ ОНИ ГОВОРЯТ О ТОМ, ЧТО 
МЕТОД ПУЗЫРЬКА ВОВСЕ НЕ ТАК УЖ ХОРОШ. пО СРАВНЕНИЮ С ПРОСТЫМИ ВСТАВКАМИ 
(АЛГОРИТМ~5.2.1S) МЕТОД ПУЗЫРЬКА ОПИСЫВАЕТСЯ БОЛЕЕ СЛОЖНОЙ ПРОГРАММОЙ 
И ТРЕБУЕТ ПРИМЕРНО В 2~РАЗА БОЛЬШЕ ВРЕМЕНИ!

мОЖНО ПРЕДЛОЖИТЬ НЕСКОЛЬКО ПУТЕЙ УЛУЧШЕНИЯ МЕТОДА ПУЗЫРЬКА. нАПРИМЕР, НА 
РИС.~14 ПЕРВОЕ СРАВНЕНИЕ В 4-М ПРОСМОТРЕ ИЗЛИШНЕ, ТАК ЖЕ КАК И ПЕРВЫЕ ДВА 
СРАВНЕНИЯ В 5-М ПРОСМОТРЕ И ПЕРВЫЕ ТРИ В 6-М И 7-М ПРОСМОТРАХ. зАМЕТИМ 
ТАКЖЕ, ЧТО ЗА ОДИН ПРОСМОТР ЭЛЕМЕНТ НЕ МОЖЕТ ПЕРЕМЕСТИТЬСЯ БОЛЕЕ ЧЕМ 
НА ОДНУ ПОЗИЦИЮ ВЛЕВО; ТАК ЧТО ЕСЛИ НАИМЕНЬШИЙ ЭЛЕМЕНТ ВНАЧАЛЕ
%%136
НАХОДИЛСЯ В ПРАВОМ КОНЦЕ, ТО МЫ ВЫНУЖДЕНЫ ВЫПОЛНИТЬ МАКСИМАЛЬНОЕ ЧИСЛО 
СРАВНЕНИЙ. эТО НАВОДИТ НА МЫСЛЬ О "ШЕЙКЕР-СОРТИРОВКЕ", КОГДА ФАЙЛ 
ПРОСМАТРИВАЕТСЯ ПОПЕРЕМЕННО В ОБОИХ НАПРАВЛЕНИЯХ (РИС.~16). пРИ ТАКОМ 
ПОДХОДЕ СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ НЕСКОЛЬКО СОКРАЩАЕТСЯ. к.~э.~аЙВЕРСОН [A 
Programming Language (Wiley, 1962), 218--219] СДЕЛАЛ ИНТЕРЕСНОЕ В ЭТОМ 
ОТНОШЕНИИ НАБЛЮДЕНИЕ: ЕСЛИ~$j$---ТАКОЙ ИНДЕКС, ЧТО~$R_j$ И~$R_{j+1}$ НЕ 
МЕНЯЮТСЯ МЕСТАМИ ПРИ ДВУХ ПОСЛЕДОВАТЕЛЬНЫХ ПРОСМОТРАХ
\picture{рИС.~16.  "шЕЙКЕР-СОРТИРОВКА".}
В ПРОТИВОПОЛОЖНЫХ НАПРАВЛЕНИЯХ, ТО ЗАПИСИ~$R_j$ И~$R_{j+1}$ 
ДОЛЖНЫ ЗАНИМАТЬ СВОИ ОКОНЧАТЕЛЬНЫЕ ПОЗИЦИИ, И ОНИ МОГУТ НЕ УЧАСТВОВАТЬ В 
ПОСЛЕДУЮЩИХ СРАВНЕНИЯХ. нАПРИМЕР, ПРОСМАТРИВАЯ ПЕРЕСТАНОВКУ 
$4\,3\,2\,1\,8\,6\,9\,7\,5$ СЛЕВА НАПРАВО, ПОЛУЧАЕМ $3\,2\,1\,4\,6\,8\,7\,5\,9$: 
ЗАПИСИ~$R_4$ И~$R_5$ НЕ ПОМЕНЯЛИСЬ МЕСТАМИ. пРИ ПРОСМОТРЕ ПОСЛЕДНЕЙ 
ПЕРЕСТАНОВКИ СПРАВА НАЛЕВО $R_4$ ВСЕ ЕЩЕ МЕНЬШЕ (НОВОЙ) ЗАПИСИ~$R_5$; 
СЛЕДОВАТЕЛЬНО, МОЖНО СРАЗУ ЖЕ СДЕЛАТЬ ВЫВОД О ТОМ, ЧТО ЗАПИСИ~$R_4$ 
И~$R_5$ МОГУТ И НЕ УЧАСТВОВАТЬ НИ В ОДНОМ ИЗ ПОСЛЕДУЮЩИХ, СРАВНЕНИЙ.

оДНАКО НИ ОДНО ИЗ ЭТИХ УСОВЕРШЕНСТВОВАНИЙ НЕ ПРИВОДИТ К ЛУЧШЕМУ АЛГОРИТМУ, 
ЧЕМ АЛГОРИТМ СОРТИРОВКИ ПРОСТЫМИ ВСТАВКАМИ,
%%137
А МЫ УЖЕ ЗНАЕМ, ЧТО ДАЖЕ ОН НЕ ГОДИТСЯ ПРИ БОЛЬШИХ~$N$. дРУГАЯ ИДЕЯ 
СОСТОИТ В ТОМ, ЧТОБЫ ИЗБЕЖАТЬ БОЛЬШИНСТВА ОБМЕНОВ. тАК КАК БОЛЬШАЯ ЧАСТЬ 
ЭЛЕМЕНТОВ ВО ВРЕМЯ ОБМЕНОВ ПРОСТО СДВИГАЕТСЯ НА ОДИН ШАГ ВЛЕВО, ТО МОЖНО 
БЫЛО БЫ ДОСТИЧЬ ТОГО ЖЕ ЭФФЕКТА, ИНАЧЕ РАССМАТРИВАЯ МАССИВ---СМЕСТИВ 
НАЧАЛО ОТСЧЕТА! нО ПОЛУЧЕННЫЙ АЛГОРИТМ НЕ ПРЕВОСХОДИТ МЕТОДА ПРОСТОГО 
\emph{ВЫБОРА} (АЛГОРИТМ~5.2.3S), КОТОРЫЙ МЫ ИЗУЧИМ ПОЗЖЕ.

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

\section пАРАЛЛЕЛЬНАЯ СОРТИРОВКА бЭТЧЕРА. еСЛИ МЫ ХОТИМ ПОЛУЧИТЬ АЛГОРИТМ 
ОБМЕННОЙ СОРТИРОВКИ, ВРЕМЯ РАБОТЫ КОТОРОГО ИМЕЕТ ПОРЯДОК, МЕНЬШИЙ~$N^2$, 
ТО НЕОБХОДИМО ПОДБИРАТЬ ДЛЯ СРАВНЕНИЙ НЕКОТОРЫЕ ПАРЫ \emph{НЕСОСЕДНИХ} 
КЛЮЧЕЙ~$(K_i, K_j)$; ИНАЧЕ ПРИДЕТСЯ
\picture{рИС.~17. аЛГОРИТМ~M.}
ВЫПОЛНИТЬ СТОЛЬКО ОБМЕНОВ, СКОЛЬКО ИНВЕРСИЙ ИМЕЕТСЯ В ИСХОДНОЙ 
ПЕРЕСТАНОВКЕ, А СРЕДНЕЕ ЧИСЛО ИНВЕРСИЙ РАВНО~$(N^2-N)/4$. в 1964~Г.\ 
к.~э.~бЭТЧЕР 
[Proc. AFIPS Spring Joint Computer Conference, {\bf 32} (1968), 307--314]
ОТКРЫЛ ОДИН ИСКУСНЫЙ СПОСОБ ЗАПРОГРАММИРОВАТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ 
СРАВНЕНИЙ, ПРЕДНАЗНАЧЕННУЮ ДЛЯ ОТЫСКАНИЯ ВОЗМОЖНЫХ ОБМЕНОВ. еГО МЕТОД 
ДАЛЕКО НЕ ОЧЕВИДЕН. в САМОМ ДЕЛЕ, ТОЛЬКО ДЛЯ ТОГО, ЧТОБЫ ПОКАЗАТЬ ЕГО 
СПРАВЕДЛИВОСТЬ, ТРЕБУЕТСЯ ВЕСЬМА СЛОЖНОЕ ДОКАЗАТЕЛЬСТВО, ТАК КАК 
ВЫПОЛНЯЕТСЯ, ОТНОСИТЕЛЬНО МАЛО СРАВНЕНИЙ. мЫ ОБСУДИМ ДВА ДОКАЗАТЕЛЬСТВА, 
ОДНО В ЭТОМ ПУНКТЕ И ОДНО В П.~5.3.4.

сХЕМА СОРТИРОВКИ бЭТЧЕРА НЕСКОЛЬКО НАПОМИНАЕТ СОРТИРОВКУ шЕЛЛА, НО 
СРАВНЕНИЯ ВЫПОЛНЯЮТСЯ ПО-НОВОМУ, ТАК ЧТО РАСПРОСТРАНЕНИЕ ОБМЕНОВ НЕ 
ОБЯЗАТЕЛЬНО. тАК, МОЖНО СРАВНИТЬ ТАБЛ.~1 С ТАБЛ.~5.2.1-3. сОРТИРОВКА 
бЭТЧЕРА ДЕЙСТВУЕТ КАК 8-СОРТИРОВКА, 4-СОРТИРОВКА, 2-СОРТИРОВКА И 
1-СОРТИРОВКА, НО СРАВНЕНИЯ НЕ
%%138
ПЕРЕКРЫВАЮТСЯ. тАК КАК В АЛГОРИТМЕ бЭТЧЕРА, ПО СУЩЕСТВУ, ПРОИСХОДИТ 
СЛИЯНИЕ ПАР ОТСОРТИРОВАННЫХ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ, ТО ЕГО МОЖНО НАЗВАТЬ 
"ОБМЕННОЙ СОРТИРОВКОЙ СО СЛИЯНИЕМ".

\alg M.(оБМЕННАЯ СОРТИРОВКА СО СЛИЯНИЕМ.) зАПИСИ$R_1$,~\dots, $R_N$ 
ПЕРЕРАЗМЕЩАЮТСЯ НА ТОМ ЖЕ МЕСТЕ. пОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ ИХ КЛЮЧИ 
БУДУТ УПОРЯДОЧЕНЫ: $K_1\le\ldots\le K_N$.  пРЕДПОЛАГАЕТСЯ, ЧТО~$N\ge2$.

\st[нАЧАЛЬНАЯ УСТАНОВКА~$p$.] уСТАНОВИТЬ~$p\asg 2^{t-1}$, 
ГДЕ~$t=\ceil{\log_2 N}$---НАИМЕНЬШЕЕ ЦЕЛОЕ ЧИСЛО, ТАКОЕ, ЧТО~$2^t\ge N$. 
(шАГИ~\stp{2},~\dots, \stp{5} БУДУТ ВЫПОЛНЯТЬСЯ С~$p=2^{t-1}$, 
$2^{t-2}$,~\dots, $1$.)

\st[нАЧАЛЬНАЯ УСТАНОВКА~$q$, $r$, $d$.] уСТАНОВИТЬ~$q\asg 2^{t-1}$, $r\asg 0$, 
$d\asg p$.

\st[цИКЛ ПО~$t$.] дЛЯ ВСЕХ~$t$, ТАКИХ, ЧТО~$0\le i < N-d$ И~$i\land p=r$,
ВЫПОЛНИТЬ ШАГ~\stp{4}. зАТЕМ ПЕРЕЙТИ К ШАГУ~\stp{5}. (зДЕСЬ ЧЕРЕЗ~$i\land p$ 
ОБОЗНАЧЕНА ОПЕРАЦИЯ "ЛОГИЧЕСКОЕ И" НАД ДВОИЧНЫМИ ПРЕДСТАВЛЕНИЯМИ 
ЧИСЕЛ~$i$ И~$p$; ВСЕ БИТЫ РЕЗУЛЬТАТА РАВНЫ~$0$, КРОМЕ ТЕХ, ДЛЯ КОТОРЫХ В 
СООТВЕТСТВУЮЩИХ ПОЗИЦИЯХ~$i$ И~$p$ НАХОДЯТСЯ ЕДИНИЧНЫЕ БИТЫ. 
тАК, $13\land 21=(1101)_2\land (10101)_2=(00101)_2=5$. к ЭТОМУ 
МОМЕНТУ~$d$---НЕЧЕТНОЕ КРАТНОЕ~$p$ (Т.~Е.\ ЧАСТНОЕ ОТ ДЕЛЕНИЯ~$d$ НА~$p$ 
НЕЧЕТНО), А~$p$---СТЕПЕНЬ ДВОЙКИ, ТАК ЧТО~$i\land p \ne (i+d)\land p$; 
ОТСЮДА СЛЕДУЕТ, ЧТО ДЕЙСТВИЯ ШАГА~\stp{4} МОЖНО ВЫПОЛНЯТЬ ПРИ ВСЕХ 
НУЖНЫХ ЗНАЧЕНИЯХ~$i$ В ЛЮБОМ ПОРЯДКЕ ИЛИ ДАЖЕ ОДНОВРЕМЕННО.)

\st[сРАВНЕНИЕ/ОБМЕН~$R_{i+1}:R_{i+d+1}$.] еСЛИ~$K_{i+1}>K_{i+d+1}$,  ТО 
ПОМЕНЯТЬ МЕСТАМИ~$R_{i+1}\xchg R_{i+d+1}$.

\st[цИКЛ ПО~$q$.] еСЛИ~$q\ne p$, ТО УСТАНОВИТЬ~$d\asg q-p$, $q\asg q/2$,
$r\asg p$ И ВОЗВРАТИТЬСЯ К ШАГУ~\stp{3}.

\st[цИКЛ ПО~$p$.] (к ЭТОМУ МОМЕНТУ ПЕРЕСТАНОВКА~$K_1\,K_2\,\ldots\,K_N$ 
БУДЕТ $p$-УПОРЯДОЧЕНА.) уСТАНОВИТЬ~$p\asg \floor{p/2}$. еСЛИ~$p>0$, 
ТО ВОЗВРАТИТЬСЯ К ШАГУ~\stp{2}.
\algend

в ТАБЛ.~1 ЭТОТ МЕТОД ПРОИЛЛЮСТРИРОВАН ПРИ~$N=16$. зАМЕТИМ, ЧТО АЛГОРИТМ 
СОРТИРУЕТ $N$~ЭЛЕМЕНТОВ, ПО СУЩЕСТВУ, ПУТЕМ НЕЗАВИСИМОЙ СОРТИРОВКИ 
ПОДФАЙЛОВ~$R_1$, $R_3$, $R_5$,~\dots{} И~$R_2$, $R_4$, $R_6$,~\dots, ПОСЛЕ 
ЧЕГО ВЫПОЛНЯЮТСЯ ШАГИ~M2,~\dots, M5 С~$p=1$, ЧТОБЫ СЛИТЬ ДВЕ 
ОТСОРТИРОВАННЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ.

чТОБЫ ДОКАЗАТЬ, ЧТО МАГИЧЕСКАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ СРАВНЕНИЙ/ОБМЕНОВ, 
ОПИСАННАЯ В АЛГОРИТМЕ~M, ДЕЙСТВИТЕЛЬНО СОРТИРУЕТ ЛЮБОЙ 
ФАЙЛ~$R_1\,R_2\,\ldots\,R_N$, МЫ ДОЛЖНЫ ПОКАЗАТЬ ТОЛЬКО, ЧТО В РЕЗУЛЬТАТЕ 
ВЫПОЛНЕНИЯ ШАГОВ ОТ~M2 ДО~M5 С~$p=1$ БУДЕТ СЛИТ ЛЮБОЙ 2-УПОРЯДОЧЕННЫЙ 
ФАЙЛ~$R_1\,R_2\,\ldots\,R_N$. дЛЯ ЭТОЙ ЦЕЛИ МОЖНО ВОСПОЛЬЗОВАТЬСЯ МЕТОДОМ 
РЕШЕТОЧНЫХ ДИАГРАММ ИЗ П.~5.2.1 (СМ.~РИС.~11); КАЖДАЯ 2-УПОРЯДОЧЕННАЯ 
ПЕРЕСТАНОВКА МНОЖЕСТВА~$\set{1, 2,~\ldots, N}$ СООТВЕТСТВУЕТ НА РЕШЕТКЕ 
ЕДИНСТВЕННОМУ ПУТИ ИЗ ВЕРШИНЫ~$(0,0)$ В~$(\ceil{N/2}, \floor{N/2})$. 
нА РИС.~18(А) ПОКАЗАН
%%139
\picture{тАБЛИЦА~1. p.139}
ПРИМЕР ПРИ~$N=16$, СООТВЕТСТВУЮЩИЙ ПЕРЕСТАНОВКЕ 
$1\,3\,2\,4\,10\,5\,11\,6\,13\,7\,14\,8\,15\,9\,16\,12$. 
дЕЙСТВИЕ ШАГА~M3 ПРИ~$p=1$, $q=2^{t-1}$, 
$r=0$, $d=1$ СОСТОИТ В СРАВНЕНИИ (И, ВОЗМОЖНО, ОБМЕНЕ) ЗАПИСЕЙ~$R_1:R_2$, 
$R_3:R_4$ И~Т.~Д. эТОЙ ОПЕРАЦИИ СООТВЕТСТВУЕТ ПРОСТОЕ ПРЕОБРАЗОВАНИЕ 
РЕШЕТОЧНОГО ПУТИ: "ПЕРЕГИБ" ОТНОСИТЕЛЬНО ДИАГОНАЛИ, ЕСЛИ НЕОБХОДИМО, ТАК,
ЧТОБЫ ПУТЬ НИГДЕ НЕ ПРОХОДИЛ ВЫШЕ ДИАГОНАЛИ. (сМ.~РИС.~18(b) И 
ДОКАЗАТЕЛЬСТВО В УПР.~10.) дЕЙСТВИЕ ПОСЛЕДУЮЩИХ ПОВТОРЕНИЙ ШАГА~M3 
С~$p=r=1$ И~$d=2^{t-1}-1$, $2^{t-2}-1$,~\dots, $1$ СОСТОИТ В 
СРАВНЕНИИ/ОБМЕНЕ ЗАПИСЕЙ~$R_2:R_{2+d}$, $R_4:R_{4+d}$ И~Т.~Д., И ОПЯТЬ 
ИМЕЕТСЯ ПРОСТАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ: ПУТЬ "ПЕРЕГИБАЕТСЯ" 
ОТНОСИТЕЛЬНО ПРЯМОЙ, РАСПОЛОЖЕННОЙ НА $(d+l)/2$~ЕДИНИЦ НИЖЕ ДИАГОНАЛИ 
(СМ.~РИС.~18(c) И~(d)). в КОНЦЕ КОНЦОВ ПРИХОДИМ К ПУТИ, ИЗОБРАЖЕННОМУ НА 
РИС.~18(e), КОТОРЫЙ СООТВЕТСТВУЕТ ПОЛНОСТЬЮ ОТСОРТИРОВАННОЙ 
ПЕРЕСТАНОВКЕ. нА ЭТОМ "ГЕОМЕТРИЧЕСКОЕ ДОКАЗАТЕЛЬСТВО" СПРАВЕДЛИВОСТИ АЛГО-
%%140
\bye