\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