\input style
%% 109
\picture{рИС. 11. сООТВЕТСТВИЕ МЕЖДУ 2-УПОРЯДОЧЕНИЕМ И ПУТЯМИ НА РЕШЕТКЕ. 
кУРСИВОМ НАБРАНЫ ВЕСА, СООТВЕТСТВУЮЩИЕ ЧИСЛУ ИНВЕРСИЙ В 2-УПОРЯДОЧЕННОЙ 
ПЕРЕСТАНОВКЕ.}

пУСТЬ $A_n$---СУММАРНОЕ ЧИСЛО ИНВЕРСИЙ ВО ВСЕХ 2-УПОРЯДОЧЕННЫХ 
ПЕРЕСТАНОВКАХ МНОЖЕСТВА $\{1, 2, \ldots, n\}$. яСНО, ЧТО $A_1=0$, $A_2=1$, 
$A_3=2$, А ИЗ РАССМОТРЕНИЯ ШЕСТИ СЛУЧАЕВ
$$
1\ 3\ 2\ 4\quad   1\ 2\ 3\ 4 \quad 1\ 2\ 4\ 3\quad   2\ 1\ 3\ 4\quad   2\ 
1\ 4\ 3   \quad 3\ 1\ 4\ 2
$$
НАХОДИМ, ЧТО $A_4=1+0+1+1+2+3=8$. чТОБЫ ИССЛЕДОВАТЬ $A_n$ В ОБЩЕМ СЛУЧАЕ, 
РАССМОТРИМ РЕШЕТЧАТУЮ ДИАГРАММУ НА РИС.~11 ДЛЯ $n=15$. в ТАКОЙ ДИАГРАММЕ 
2-УПОРЯДОЧЕННУЮ ПЕРЕСТАНОВКУ МОЖНО ПРЕДСТАВИТЬ В ВИДЕ ПУТИ ИЗ ВЕРХНЕЙ 
ЛЕВОЙ УГЛОВОЙ ТОЧКИ $(0, 0)$ В НИЖНЮЮ ПРАВУЮ УГЛОВУЮ ТОЧКУ $(\ceil{n/2}, 
\floor{n/2})$, ЕСЛИ ДЕЛАТЬ $k$-Й ШАГ ПУТИ ВПРАВО ИЛИ ВНИЗ В СООТВЕТСТВИИ С 
ТЕМ, НАХОДИТСЯ ЛИ $k$ В ЧЕТНОЙ ИЛИ НЕЧЕТНОЙ ПОЗИЦИИ ПЕРЕСТАНОВКИ. эТИМ 
ПРАВИЛОМ ОПРЕДЕЛЯЕТСЯ ВЗАИМНО ОДНОЗНАЧНОЕ СООТВЕТСТВИЕ МЕЖДУ 
2-УПОРЯДОЧЕННЫМИ ПЕРЕСТАНОВКАМИ И $n$-ШАГОВЫМИ ПУТЯМИ ИЗ ОДНОГО УГЛА 
РЕШЕТЧАТОЙ ДИАГРАММЫ В ДРУГОЙ. нАПРИМЕР, ИЗОБРАЖЕННЫЙ НА РИСУНКЕ ПУТЬ 
СООТВЕТСТВУЕТ ПЕРЕСТАНОВКЕ
$$
2\ 1\ 3\ 4\ 6\ 5\ 7\ 10\ 8\ 11\ 9\ 12\ 14\ 13\ 15.
\eqno(1)
$$
дАЛЕЕ, ВЕРТИКАЛЬНЫМ ОТРЕЗКАМ ПУТИ МОЖНО ПРИПИСАТЬ "ВЕСА", КАК ПОКАЗАНО НА 
ДИАГРАММЕ; ОТРЕЗКУ, ВЕДУЩЕМУ ИЗ ТОЧКИ $(i, j)$
%% 110
В ТОЧКУ $(i+1, j)$ ПРИПИСЫВАЕТСЯ ВЕС $\abs{i-j}$. нЕМНОГО ПОДУМАВ,
ЧИТАТЕЛЬ УБЕДИТСЯ В ТОМ, ЧТО СУММА ЭТИХ ВЕСОВ ВДОЛЬ КАЖДОГО ПУТИ РАВНА 
ЧИСЛУ ИНВЕРСИЙ В СООТВЕТСТВУЮЩЕЙ ПЕРЕСТАНОВКЕ (СМ. УПР.~12). тАК, НАПРИМЕР,
ПЕРЕСТАНОВКА (1) СОДЕРЖИТ 
$1+0+1+0+1+2+1=6$ ИНВЕРСИЙ.

еСЛИ $a\le a'$ И~$b\le b'$, ТО ЧИСЛО ДОПУСТИМЫХ ПУТЕЙ ИЗ $(a, b)$ В 
$(a', b')$ РАВНО ЧИСЛУ СПОСОБОВ ПЕРЕМЕШАТЬ $a'-a$ ВЕРТИКАЛЬНЫХ ОТРЕЗКОВ 
С $b'-b$ ГОРИЗОНТАЛЬНЫМИ, А ИМЕННО
$$
\perm{a'-a+b'-b}{a'-a}.
$$
сЛЕДОВАТЕЛЬНО, ЧИСЛО ПЕРЕСТАНОВОК, ДЛЯ КОТОРЫХ СООТВЕТСТВУЮЩИЕ ПУТИ 
ПРОХОДЯТ ЧЕРЕЗ ВЕРТИКАЛЬНЫЙ ОТРЕЗОК ИЗ $(i, j)$ В~$(i+1, j)$, РАВНО
$$
\perm{i+j}{i}\perm{n-i-j-1}{\floor{n/2}-j}.
$$
уМНОЖАЯ ЭТО ЗНАЧЕНИЕ НА ВЕС ДАННОГО ОТРЕЗКА И СУММИРУЯ ПО ВСЕМ ОТРЕЗКАМ, ПОЛУЧАЕМ
$$
\eqalign{
A_{2n}&=\sum_{0\le i\le n \atop 0\le j\le n}
\abs{i-j}\perm{i+j}{i}\perm{2n-i-j-1}{n-j};\cr
A_{2n+1}&=\sum_{0\le i\le n \atop 0\le j\le n}
\abs{i-j}\perm{i+j}{i}\perm{2n-i-j}{n-j};\cr
}
\eqno(2)
$$
зНАКИ АБСОЛЮТНОЙ ВЕЛИЧИНЫ В ЭТИХ СУММАХ НЕСКОЛЬКО УСЛОЖНЯЮТ ВЫЧИСЛЕНИЯ, НО 
В УПР.~14 ПОКАЗАНО, ЧТО ВЕЛИЧИНА $A_n$ ИМЕЕТ УДИВИТЕЛЬНО ПРОСТОЙ ВИД: 
$\floor{n/2}2^{n-2}$. сЛЕДОВАТЕЛЬНО, СРЕДНЕЕ ЧИСЛО ИНВЕРСИЙ В СЛУЧАЙНОЙ 
2-УПОРЯДОЧЕННОЙ ПЕРЕСТАНОВКЕ РАВНО
$$
\floor{n/2}2^{n-2}/\perm{n}{\floor{n/2}}.
$$
пО ФОРМУЛЕ сТИРЛИНГА ЭТА ВЕЛИЧИНА АСИМПТОТИЧЕСКИ ПРИБЛИЖАЕТСЯ К 
$\sqrt{\pi/128}n^{3/2}\approx 0.15 n^{3/2}$. кАК ЛЕГКО ВИДЕТЬ, 
МАКСИМАЛЬНОЕ ЧИСЛО ИНВЕРСИЙ РАВНО
$$
\perm{\floor{n/2}+1}{2}\approx{1\over8}n^2.
$$
пОЛЕЗНО ИССЛЕДОВАТЬ РАСПРЕДЕЛЕНИЕ ЧИСЛА ИНВЕРСИЙ БОЛЕЕ ТЩАТЕЛЬНО, 
РАССМОТРЕВ ПРОИЗВОДЯЩИЕ ФУНКЦИИ
$$
\matrix{
 h_1(z)=1, \quad h_2(z)=1+z,\cr
 h_3(z)=1+2z, \quad h_4(z)=1+3z+z^2+z^3, \ldots,\cr
}
\eqno(3)
$$
%% 111
КАК В УПР. 15. тАКИМ ОБРАЗОМ, НАЙДЕМ, ЧТО СТАНДАРТНОЕ ОТКЛОНЕНИЕ ТОЖЕ 
ПРОПОРЦИОНАЛЬНО $n^{3/2}$, ТАК ЧТО ЧИСЛО ИНВЕРСИЙ НЕ СЛИШКОМ УСТОЙЧИВО 
РАСПРЕДЕЛЕНО ОКОЛО СВОЕГО СРЕДНЕГО ЗНАЧЕНИЯ. рАССМОТРИМ ТЕПЕРЬ ОБЩИЙ 
ДВУХПРОХОДНЫЙ СЛУЧАЙ АЛГОРИТМА D, КОГДА ШАГИ СОРТИРОВКИ РАВНЫ $h$ И~1.

\proclaim тЕОРЕМА H. сРЕДНЕЕ ЧИСЛО ИНВЕРСИЙ В $h$-УПОРЯДОЧЕННОЙ 
ПЕРЕСТАНОВКЕ МНОЖЕСТВА $\{1, 2, \ldots, n\}$ РАВНО
$$
f(n, h)={2^{2q-1}q!q! \over (2q+1)!}\left(\left({h\over2}\right)q(q+1)+
\left({r\over2}\right)(q+1)-{1\over2}\perm{h-r}{2}q\right),
\eqno(4)
$$
ГДЕ $q =\floor{n/h}$, $r= n \bmod h$.
эТА ТЕОРЕМА ПРИНАДЛЕЖИТ дУГЛАСУ хАНТУ [Bachelor's thesis, Princeton 
University (April, 1967)]. зАМЕТИМ, ЧТО ФОРМУЛА СПРАВЕДЛИВА И ПРИ 
$h\ge n: f (n, h) ={1\over2}\left({n\over2}\right)$.
\proof в $h$-УПОРЯДОЧЕННОЙ ПЕРЕСТАНОВКЕ СОДЕРЖИТСЯ 
$r$ УПОРЯДОЧЕННЫХ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЛИНЫ $q+1$ И $h-r$ 
ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЛИНЫ $q$. кАЖДАЯ ИНВЕРСИЯ ОБРАЗУЕТСЯ 
ИЗ ЭЛЕМЕНТОВ ДВУХ РАЗЛИЧНЫХ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ, А КАЖДАЯ ПАРА 
РАЗЛИЧНЫХ УПОРЯДОЧЕННЫХ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ В СЛУЧАЙНОЙ 
$h$-УПОРЯДОЧЕННОЙ ПЕРЕСТАНОВКЕ ОПРЕДЕЛЯЕТ СЛУЧАЙНУЮ 2-УПОРЯДОЧЕННУЮ 
ПЕРЕСТАНОВКУ. пОЭТОМУ СРЕДНЕЕ ЧИСЛО ИНВЕРСИЙ РАВНО СУММЕ СРЕДНИХ ЗНАЧЕНИЙ 
ЧИСЛА ИНВЕРСИЙ ВО ВСЕХ ПАРАХ РАЗЛИЧНЫХ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ, А ИМЕННО
$$
\perm{r}{2}{A_{2q+2}\over\perm{2q+2}{q+1}}
+r(h-r){A_{2q+1}\over\perm{2q+1}{q}}
+\perm{h-r}{2}{A_{2q}\over\perm{2q}{q}}=f(n,h).\;\endmark
$$
\eproofend

\proclaim сЛЕДСТВИЕ. еСЛИ ПОСЛЕДОВАТЕЛЬНОСТЬ ПРИРАЩЕНИЙ УДОВЛЕТВОРЯЕТ УСЛОВИЮ
$$
h_{s+1}\bmod h_s=0\rem{ ПРИ $t>s\ge 1$,}
\eqno(5)
$$
ТО СРЕДНЕЕ ЧИСЛО ОПЕРАЦИЙ ПЕРЕМЕЩЕНИЯ В АЛГОРИТМЕ D РАВНО
$$
\sum_{t\ge s\ge 1}
 (r_sf(q_s+1, h_{s+1}/h_s)+(h_s-r_s)f(q_s, h_{s+1}/h_s)),
\eqno(6)
$$
ГДЕ $r_s=N\bmod h_s$, $q_s=\floor{N/h_s}$, $h_{t+1}=Nh_t$, А ФУНКЦИЯ $f$ 
ОПРЕДЕЛЯЕТСЯ ФОРМУЛОЙ (4).

\proof пРОЦЕСС $h_s$-СОРТИРОВКИ СОСТОИТ ИЗ СОРТИРОВКИ ПРОСТЫМИ ВСТАВКАМИ 
$r_s(h_{s+1}/h_s)$-УПОРЯДОЧЕННЫХ ПОДФАЙЛОВ ДЛИНЫ $q_s+1$ 
И~$(h_s-r_s)$ ТАКИХ ПОДФАЙЛОВ ДЛИНЫ $q_s$. пОСКОЛЬКУ МЫ ПРЕДПОЛАГАЕМ, ЧТО 
ИСХОДНАЯ ПЕРЕСТАНОВКА СЛУЧАЙНА И ВСЕ ЕЕ ЭЛЕМЕНТЫ РАЗЛИЧНЫ, ТО ИЗ УСЛОВИЙ 
ДЕЛИМОСТИ СЛЕДУЕТ, ЧТО КАЖДЫЙ ИЗ ПОДФАЙЛОВ---"СЛУЧАЙНАЯ" 
$(h_{s+1}/h_s)$-УПОРЯДОЧЕННАЯ
%%112
ПЕРЕСТАНОВКА В ТОМ СМЫСЛЕ, ЧТО ВСЕ 
$(h_{s+1}/h_s)$-УПОРЯДОЧЕННЫЕ ПЕРЕСТАНОВКИ РАВНОВЕРОЯТНЫ.
\proofend

уСЛОВИЕ (5) ЭТОГО СЛЕДСТВИЯ ВСЕГДА ВЫПОЛНЯЕТСЯ ДЛЯ \emph{ДВУХПРОХОДНОЙ} 
СОРТИРОВКИ МЕТОДОМ шЕЛЛА, КОГДА ШАГИ РАВНЫ СООТВЕТСТВЕННО $h$ И~1. 
пУСТЬ $q=\floor{N/h}$, a~$r=N\bmod h$, ТОГДА СРЕДНЕЕ ЗНАЧЕНИЕ ВЕЛИЧИНЫ $B$ 
В ПРОГРАММЕ D РАВНО
$$
rf(q+1, N)+(h-r)f(q, N)+f(N,h)
={r\over2}\perm{q+1}{2}+{h-r\over2}\perm{q}{2}+f(N,h).
$$
в ПЕРВОМ ПРИБЛИЖЕНИИ ФУНКЦИЯ $f(n, h)$ РАВНА $(\sqrt{\pi}/8)n^{3/2}h^{1/2}$;
СР. С ГЛАДКОЙ КРИВОЙ НА РИС.~12. сЛЕДОВАТЕЛЬНО, ВРЕМЯ РАБОТЫ
\picture{рИС. 12. сРЕДНЕЕ ЧИСЛО ИНВЕРСИЙ $f(n, h)$ В $h$-УПОРЯДОЧЕННОМ 
ФАЙЛЕ ИЗ $n$ ЭЛЕМЕНТОВ ДЛЯ СЛУЧАЯ $n=64$.}
ДВУХПРОХОДНОЙ ПРОГРАММЫ D ПРИМЕРНО ПРОПОРЦИОНАЛЬНО 
$2N^2/h+\sqrt{\pi N^3h}$. пОЭТОМУ НАИЛУЧШЕЕ ЗНАЧЕНИЕ $h$ РАВНО 
ПРИБЛИЗИТЕЛЬНО $\root 3\of{16N/\pi}\approx1.72\root3\of{N}$; ПРИ ТАКОМ 
ВЫБОРЕ $h$ СРЕДНЕЕ ВРЕМЯ РАБОТЫ ПРОПОРЦИОНАЛЬНО $N^{5/3}$.

тАКИМ ОБРАЗОМ, ДАЖЕ ПРИМЕНЯЯ МЕТОД шЕЛЛА С ВСЕГО ДВУМЯ ШАГАМИ, МОЖНО 
СУЩЕСТВЕННО СОКРАТИТЬ ВРЕМЯ ПО СРАВНЕНИЮ С ПРОСТЫМИ ВСТАВКАМИ, С $O(N^2)$ 
ДО~$O(N^{1.667})$. яСНО, ЧТО МОЖНО ДОБИТЬСЯ ЛУЧШИХ РЕЗУЛЬТАТОВ, ЕСЛИ 
ИСПОЛЬЗОВАТЬ БОЛЬШЕ ШАГОВ. в УПР.~18 ОБСУЖДАЕТСЯ ОПТИМАЛЬНЫЙ ВЫБОР 
$h_t$,~\dots, $h_1$ ПРИ ФИКСИРОВАННОМ~$t$
%%113
В СЛУЧАЕ, КОГДА ЗНАЧЕНИЯ $h$ ОГРАНИЧЕНЫ 
УСЛОВИЕМ ДЕЛИМОСТИ; ВРЕМЯ РАБОТЫ ПРИ БОЛЬШИХ $N$ СОКРАЩАЕТСЯ 
ДО $O(N^{1.5+\varepsilon/2}$ ГДЕ $\varepsilon=1/(2^t-1)$. еСЛИ МЫ 
ПОЛЬЗУЕМСЯ ПРИВЕДЕННЫМИ ВЫШЕ ФОРМУЛАМИ, БАРЬЕР $N^{1.5}$ ПРЕОДОЛЕТЬ 
НЕВОЗМОЖНО, ПОТОМУ ЧТО ПРИ ПОСЛЕДНЕМ ПРОСМОТРЕ В СУММУ ИНВЕРСИЙ ВСЕГДА ВНОСИТСЯ ВКЛАД
$$
f(N, h_2)\approx(\sqrt{\pi}/8)N^{3/2}h_2^{1/2}.
$$

нО ИНТУИЦИЯ ПОДСКАЗЫВАЕТ, ЧТО, ЕСЛИ ШАГИ $h_t$, \dots, $h_1$ 
\emph{НЕ БУДУТ} УДОВЛЕТВОРЯТЬ УСЛОВИЮ ДЕЛИМОСТИ (5), МОЖНО 
ДОСТИЧЬ БОЛЬШЕГО. нАПРИМЕР, ПРИ ПОСЛЕДОВАТЕЛЬНОМ ВЫПОЛНЕНИИ 8-, 4- И 
2-СОРТИРОВОК НЕВОЗМОЖНО ВЗАИМОДЕЙСТВИЕ МЕЖДУ КЛЮЧАМИ В ЧЕТНЫХ И НЕЧЕТНЫХ 
ПОЗИЦИЯХ; ПОЭТОМУ НА ДОЛЮ ЗАКЛЮЧИТЕЛЬНОЙ 1-СОРТИРОВКИ ОСТАНЕТСЯ 
$O(N^{3/2})$ ИНВЕРСИЙ. в ТО ЖЕ ВРЕМЯ ПРИ ПОСЛЕДОВАТЕЛЬНОМ ВЫПОЛНЕНИИ 7-, 
5- И 3-СОРТИРОВОК ФАЙЛ ПЕРЕТРЯХИВАЕТСЯ ТАК, ЧТО ПРИ ЗАКЛЮЧИТЕЛЬНОЙ 
1-СОРТИРОВКЕ НЕ МОЖЕТ ВСТРЕТИТЬСЯ БОЛЕЕ $2N$ ИНВЕРСИЙ! (сМ. УПР.~26.) нА 
САМОМ ДЕЛЕ НАБЛЮДАЕТСЯ УДИВИТЕЛЬНОЕ ЯВЛЕНИЕ.

\proclaim тЕОРЕМА к. пОСЛЕ $h$-СОРТИРОВКИ $k$-УПОРЯДОЧЕННЫЙ ФАЙЛ ОСТАЕТСЯ $k$-УПОРЯДОЧЕННЫМ.

тАКИМ ОБРАЗОМ, ФАЙЛ, КОТОРЫЙ БЫЛ СНАЧАЛА 7-ОТСОРТИРОВАН, А ПОТОМ 
5-ОТСОРТИРОВАН, СТАНОВИТСЯ ОДНОВРЕМЕННО. 7- И 5-УПОРЯДОЧЕННЫМ. а ЕСЛИ МЫ 
ПОДВЕРГНЕМ ЕГО 3-СОРТИРОВКЕ, ТО ПОЛУЧЕННЫЙ ФАЙЛ БУДЕТ 7-, 5- И 
3-УПОРЯДОЧЕН. пРИМЕРЫ ПРОЯВЛЕНИЯ ЭТОГО ЗАМЕЧАТЕЛЬНОГО СВОЙСТВА МОЖНО НАЙТИ 
В ТАБЛ. 4.
\picture{тАБЛИЦА 4  сОРТИРОВКА С УБЫВАЮЩИМ ШАГОМ (7, 5, 3, 1)}
\proof в УПР.~20 ПОКАЗАНО, ЧТО ЭТА ТЕОРЕМА ВЫТЕКАЕТ ИЗ СЛЕДУЮЩЕЙ ЛЕММЫ:

%%114

\proclaim лЕММА L. пУСТЬ $m$, $n$, $r$---НЕОТРИЦАТЕЛЬНЫЕ ЦЕЛЫЕ ЧИСЛА, 
А $x_1$, \dots, $x_{m+r}$ И~$y_1$, \dots, $y_{n+r}$---ПРОИЗВОЛЬНЫЕ 
ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЕЛ, ТАКИЕ, ЧТО
$$
y_1\le x_{m+1}, y_2\le x_{m+2}, \ldots, y_r\le x_{m+r}.
\eqno(7)
$$
еСЛИ ПОСЛЕДОВАТЕЛЬНОСТИ $x$ И~$y$ ОТСОРТИРОВАТЬ НЕЗАВИСИМО, ТАК ЧТО 
$x_1\le\ldots\le x_{m+r}$ И~$y_1\le\ldots\le y_{n+r}$, ТО СООТНОШЕНИЯ (7) 
ОСТАНУТСЯ В СИЛЕ.

\proof иЗВЕСТНО, ЧТО ВСЕ, КРОМЕ, БЫТЬ МОЖЕТ, $m$ ЭЛЕМЕНТОВ 
ПОСЛЕДОВАТЕЛЬНОСТИ $x$, ПРЕВОСХОДЯТ (Т. Е. БОЛЬШЕ ИЛИ РАВНЫ) НЕКОТОРЫЕ 
ЭЛЕМЕНТЫ ПОСЛЕДОВАТЕЛЬНОСТИ $y$, ПРИЧЕМ РАЗЛИЧНЫЕ ЭЛЕМЕНТЫ $x$ 
ПРЕВОСХОДЯТ РАЗЛИЧНЫЕ ЭЛЕМЕНТЫ $y$. пУСТЬ $1\le j\le r$. тАК КАК ПОСЛЕ 
СОРТИРОВКИ ЭЛЕМЕНТ $x_{m+j}$ ПРЕВОСХОДИТ $m+j$ ЭЛЕМЕНТОВ $x$, ТО ОН 
ПРЕВОСХОДИТ ПО КРАЙНЕЙ МЕРЕ $j$ ЭЛЕМЕНТОВ $y$, А ЗНАЧИТ, ОН ПРЕВОСХОДИТ 
$j$ \emph{НАИМЕНЬШИХ} ЭЛЕМЕНТОВ $y$. сЛЕДОВАТЕЛЬНО, ПОСЛЕ СОРТИРОВКИ ИМЕЕМ 
$x_{m+j}\ge y_j$.
\endmark\hskip 1em
%\proofend
\proofend

иЗ ТЕОРЕМЫ к ВИДНО, ЧТО ПРИ СОРТИРОВКЕ ЖЕЛАТЕЛЬНО ПОЛЬЗОВАТЬСЯ ВЗАИМНО 
ПРОСТЫМИ ЗНАЧЕНИЯМИ ШАГОВ, ОДНАКО НЕПОСРЕДСТВЕННО ИЗ НЕЕ НЕ СЛЕДУЮТ 
ТОЧНЫЕ ОЦЕНКИ ЧИСЛА ПЕРЕМЕЩЕНИЙ, ВЫПОЛНЯЕМЫХ АЛГОРИТМОМ D. тАК КАК ЧИСЛО 
ПЕРЕСТАНОВОК МНОЖЕСТВА $\{1, 2, \dots, n\}$, ОДНОВРЕМЕННО $h$- И 
$k$-УПОРЯДОЧЕННЫХ, НЕ ВСЕГДА ЯВЛЯЕТСЯ ДЕЛИТЕЛЕМ $n!$, ТО ПОНЯТНО, ЧТО 
ТЕОРЕМА к ОБЎЯСНЯЕТ ДАЛЕКО НЕ ВСЕ; В РЕЗУЛЬТАТЕ $k$- И $h$-СОРТИРОВОК 
НЕКОТОРЫЕ $k$- И $h$-УПОРЯДОЧЕННЫЕ ФАЙЛЫ ПОЛУЧАЮТСЯ ЧАЩЕ ДРУГИХ. 
бОЛЕЕ ТОГО, НЕ СУЩЕСТВУЕТ ОЧЕВИДНОГО СПОСОБА ОТЫСКАТЬ "НАИХУДШИЙ СЛУЧАЙ" 
ДЛЯ АЛГОРИТМА D ПРИ ПРОИЗВОЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ШАГОВ СОРТИРОВКИ $h_t$,
 \dots, $h_1$. пОЭТОМУ ДО СИХ ПОР ВСЕ ПОПЫТКИ АНАЛИЗА ЭТОГО АЛГОРИТМА В 
ОБЩЕМ СЛУЧАЕ БЫЛИ ТЩЕТНЫ; ПО СУЩЕСТВУ, ВСЕ, ЧТО НАМ ИЗВЕСТНО,---ЭТО 
ПРИБЛИЖЕННОЕ АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ МАКСИМАЛЬНОГО ВРЕМЕНИ РАБОТЫ В НЕКОТОРЫХ СЛУЧАЯХ.

\proclaim тЕОРЕМА P. еСЛИ $h_s= 2^s-1$ ПРИ 
$1\le s\le t=\floor{\log_2 N}$, ТО ВРЕМЯ РАБОТЫ АЛГОРИТМА D ЕСТЬ $O(N^{3/2})$

\proof дОСТАТОЧНО НАЙТИ ОЦЕНКУ $B_s$ ЧИСЛА ПЕРЕМЕЩЕНИЙ ПРИ $s$-М ПРОСМОТРЕ,
 ТАКУЮ, ЧТОБЫ $B_t+\cdots+B_1=O(N^{3/2})$. дЛЯ ПЕРВЫХ $t/2$ ПРОСМОТРОВ ПРИ 
$t\le s\ge t/2$ МОЖНО ВОСПОЛЬЗОВАТЬСЯ ОЧЕВИДНОЙ ОЦЕНКОЙ 
$B_s=O(h_s(N/h_s)^2)$, a ДЛЯ ПОСЛЕДУЮЩИХ ПРОСМОТРОВ МОЖНО ПРИМЕНИТЬ 
РЕЗУЛЬТАТ УПР.~23: $B_s=O(Nh_{s+2}h_{s+1}/h_s)$. сЛЕДОВАТЕЛЬНО, 
$B_t+\cdots+B_1=O(N (2 + 2^2 +\cdots+2^{t/2}++2^{t/2}+\cdots+2))=O(N^{3/2})$.
\proofend

эТА ТЕОРЕМА ПРИНАДЛЕЖИТ а.~а.~пАПЕРНОВУ И г.~в.~сТАСЕВИЧУ [{\sl пРОБЛЕМЫ 
ПЕРЕДАЧИ ИНФОРМАЦИИ\/}, 1,3 (1965), 81--98]. оНА ДАЕТ ВЕРХНЮЮ ОЦЕНКУ 
\emph{МАКСИМАЛЬНОГО} ВРЕМЕНИ РАБОТЫ АЛГОРИТМА, А НЕ
%%115
\ctable{
\hfill\bskip$#$\bskip\hfill&&\hfill\bskip$#$\bskip\hfill\cr
\noalign{\rightline{\it тАБЛИЦА 5}}
\noalign{\centerline{\bf аНАЛИЗ АЛГОРИТМА D ПРИ $N=8$}}
\multispan{3}\hbox{шАГИ} & A_{ave} & B_{ave} & S & T & \hbox{ВРЕМЯ МАШИНЫ \MIX}\cr
  &   &1 & 1.718 &14.000 & 1 & 1 & 204.85u\cr
  & 2 & 1& 2.667 & 9.657 & 3 & 2 & 235.91u\cr
  & 3 & 1& 2.917 & 9.100 & 4 & 2 & 220.16u\cr
  & 4 & 1& 3.083 &10.000 & 5 & 2 & 217.75u\cr
  & 5 & 1& 2.601 &10.000 & 6 & 2 & 210.00u\cr
  & 6 & 1& 2.135 &10.667 & 7 & 3 & 206.60u\cr
  & 7 & 1& 1.718 &12.000 & 8 & 2 & 208.85u\cr
4 & 2 & 1& 3.500 & 8.324 & 7 & 3 & 272.32u\cr
5 & 3 & 1& 3.301 & 8.167 & 9 & 3 & 251.60u\cr
3 & 2 & 1& 3.320 & 7.829 & 6 & 3 & 278.50u\cr
}
ПРОСТО ОЦЕНКУ \emph{СРЕДНЕГО} ВРЕМЕНИ РАБОТЫ. эТОТ РЕЗУЛЬТАТ НЕТРИВИАЛЕН,
 ПОСКОЛЬКУ МАКСИМАЛЬНОЕ ВРЕМЯ РАБОТЫ В СЛУЧАЕ, КОГДА ПРИРАЩЕНИЯ $h$ 
УДОВЛЕТВОРЯЮТ УСЛОВИЮ ДЕЛИМОСТИ (5), ИМЕЕТ ПОРЯДОК $N^2$, А В УПР.~24 
ДОКАЗАНО, ЧТО ПОКАЗАТЕЛЬ $3/2$ УМЕНЬШИТЬ НЕЛЬЗЯ.

иНТЕРЕСНОЕ УЛУЧШЕНИЕ ПО СРАВНЕНИЮ С ТЕОРЕМОЙ P ОБНАРУЖИЛ В 1969~Г. вОГАН 
пРАТТ. \dfn{еСЛИ ВСЕ ШАГИ СОРТИРОВКИ ВЫБИРАЮТСЯ ИЗ МНОЖЕСТВА ЧИСЕЛ ВИДА 
$2^p3^q$, МЕНЬШИХ $N$, ТО ВРЕМЯ РАБОТЫ АЛГОРИТМА D БУДЕТ ПОРЯДКА 
$N (\log N)^2$}. в ЭТОМ СЛУЧАЕ ТАКЖЕ МОЖНО ВНЕСТИ В АЛГОРИТМ НЕСКОЛЬКО СУЩЕСТВЕННЫХ 
УПРОЩЕНИЙ. к СОЖАЛЕНИЮ, МЕТОД пРАТТА ТРЕБУЕТ СРАВНИТЕЛЬНО БОЛЬШОГО ЧИСЛА 
ПРОСМОТРОВ, ТАК ЧТО ЭТО НЕ ЛУЧШИЙ СПОСОБ ВЫБОРА ШАГОВ, ЕСЛИ ТОЛЬКО $N$ НЕ 
ОЧЕНЬ ВЕЛИКО; СМ. УПР.~30 И~31.

рАССМОТРИМ \emph{ОБЩЕЕ} ВРЕМЯ РАБОТЫ ПРОГРАММЫ D, 
ИМЕННО $(9B+10NT+13T-10S-3A+1)u$. в ТАБЛ.~5 ПОКАЗАНО СРЕДНЕЕ ВРЕМЯ РАБОТЫ 
ДЛЯ РАЗЛИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ШАГОВ ПРИ $N=8$. кАЖДЫЙ ЭЛЕМЕНТ ТАБЛИЦЫ 
МОЖНО ВЫЧИСЛИТЬ С ПОМОЩЬЮ ФОРМУЛ, ПРИВЕДЕННЫХ ВЫШЕ ИЛИ В УПР.~19, ЗА 
ИСКЛЮЧЕНИЕМ СЛУЧАЕВ, КОГДА ШАГИ РАВНЫ $5$ $3$ $1$ И $3$ $2$ $1$; ДЛЯ ЭТИХ 
ДВУХ СЛУЧАЕВ БЫЛО ПРОВЕДЕНО ТЩАТЕЛЬНОЕ ИССЛЕДОВАНИЕ ВСЕХ $8!$ 
ПЕРЕСТАНОВОК. зАМЕТИМ, ЧТО ПРИ ТАКОМ МАЛОМ ЗНАЧЕНИИ $N$ В ОБЩЕМ ВРЕМЕНИ 
РАБОТЫ ПРЕОБЛАДАЮТ ВСПОМОГАТЕЛЬНЫЕ ОПЕРАЦИИ, ПОЭТОМУ НАИЛУЧШИЕ РЕЗУЛЬТАТЫ 
ПОЛУЧАЮТСЯ ПРИ $t=1$; СЛЕДОВАТЕЛЬНО, ПРИ $N=8$ ЛУЧШЕ ВСЕГО ПОЛЬЗОВАТЬСЯ 
ПРОСТЫМИ ВСТАВКАМИ. (сРЕДНЕЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ S ПРИ $N=8$ РАВНО 
ВСЕГО $191.85u$.) лЮБОПЫТНО, ЧТО НАИЛУЧШИЙ РЕЗУЛЬТАТ В ДВУХПРОХОДНОМ 
АЛГОРИТМЕ ДОСТИГАЕТСЯ ПРИ $h_2=6$, ПОСКОЛЬКУ БОЛЬШАЯ ВЕЛИЧИНА 
5 ОКАЗЫВАЕТСЯ ВАЖНЕЕ МАЛОЙ ВЕЛИЧИНЫ~$B$. аНАЛОГИЧНО ТРИ ШАГА $3$ $2$ $1$ 
МИНИМИЗИРУЮТ СРЕДНЕЕ ЧИСЛО ПЕРЕМЕЩЕНИЙ, НО ЭТО НЕ САМАЯ
%% 116
ЛУЧШАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ДЛЯ ТРЕХ ПРОСМОТРОВ. бЫТЬ МОЖЕТ, ИНТЕРЕСНО 
ПРИВЕСТИ НЕКОТОРЫЕ "НАИХУДШИЕ" ПЕРЕСТАНОВКИ, МАКСИМИЗИРУЮЩИЕ ЧИСЛО 
ПЕРЕМЕЩЕНИЙ, ТАК КАК ОБЩИЙ СПОСОБ ПОСТРОЕНИЯ ТАКИХ ПЕРЕСТАНОВОК ДО СИХ ПОР 
НЕ ИЗВЕСТЕН:
$$
\matrix{
h_3=5, & h_2=3, & h_1=1: & 8 & 5 & 2 & 6 & 3 & 7 & 4 & 1 & \hbox{(19 ПЕРЕМЕЩЕНИЙ)}\cr
h_3=3, & h_2=2, & h_1=1: & 8 & 3 & 5 & 7 & 2 & 4 & 6 & 1 & \hbox{(17 ПЕРЕМЕЩЕНИЙ)}\cr
}
$$

с РОСТОМ $N$ НАБЛЮДАЕТСЯ НЕСКОЛЬКО ИНАЯ КАРТИНА. в ТАБЛ.~6 ПОКАЗАНЫ 
ПРИБЛИЖЕННЫЕ ЗНАЧЕНИЯ ЧИСЛА ПЕРЕМЕЩЕНИЙ ДЛЯ РАЗЛИЧНЫХ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ ШАГОВ ПРИ $N=1000$. пЕРВЫЕ 
НЕСКОЛЬКО ПОСЛЕДОВАТЕЛЬНОСТЕЙ УДОВЛЕТВОРЯЮТ УСЛОВИЮ ДЕЛИМОСТИ (5), ТАК ЧТО 
МОЖНО ВОСПОЛЬЗОВАТЬСЯ ФОРМУЛОЙ (6); ДЛЯ ПОЛУЧЕНИЯ СРЕДНИХ ЗНАЧЕНИЙ ПРИ 
ДРУГИХ ПОСЛЕДОВАТЕЛЬНОСТЯХ ШАГОВ ПРИМЕНЯЛИСЬ ЭМПИРИЧЕСКИЕ ТЕСТЫ. бЫЛИ 
СГЕНЕРИРОВАНЫ ПЯТЬ ФАЙЛОВ ПО 1000 СЛУЧАЙНЫХ ЭЛЕМЕНТОВ, И КАЖДЫЙ ФАЙЛ 
СОРТИРОВАЛСЯ С КАЖДОЙ ПОСЛЕДОВАТЕЛЬНОСТЬЮ ШАГОВ.

эТИ ДАННЫЕ ПОЗВОЛЯЮТ ВЫЯВИТЬ НЕКОТОРЫЕ ХАРАКТЕРИСТИКИ, НО ПОВЕДЕНИЕ 
АЛГОРИТМА D ВСЕ ЕЩЕ ОСТАЕТСЯ НЕЯСНЫМ. шЕЛЛ ПЕРВОНАЧАЛЬНО ПРЕДПОЛАГАЛ 
ИСПОЛЬЗОВАТЬ ШАГИ $\floor{N/2}$, $\floor{N/4}$, $\floor{N/8}$, \dots НО 
ЭТО НЕЖЕЛАТЕЛЬНО, ЕСЛИ ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ ЧИСЛА $N$ СОДЕРЖАТ ДЛИННЫЕ 
ЦЕПОЧКИ НУЛЕЙ. лАЗАРУС И фРЭНК [{\sl CACM\/}, {\bf 3} (1960), 20--22] 
ПРЕДЛОЖИЛИ ИСПОЛЬЗОВАТЬ, ПО СУЩЕСТВУ, ТУ ЖЕ ПОСЛЕДОВАТЕЛЬНОСТЬ, НО 
ДОБАВЛЯЯ $1$ ТАМ, ГДЕ ЭТО НЕОБХОДИМО, ЧТОБЫ СДЕЛАТЬ ВСЕ ШАГИ НЕЧЕТНЫМИ. 
хИББАРД 
[{\sl CACM\/}, {\bf 6} (1963), 206--213] ПРЕДЛОЖИЛ ШАГИ ВИДА $2^k-1$; 
пАПЕРНОВ И сТАСЕВИЧ ПРЕДЛОЖИЛИ ПОСЛЕДОВАТЕЛЬНОСТЬ $2^k+1$. сРЕДИ ДРУГИХ 
ЕСТЕСТВЕННЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ИСПОЛЬЗОВАННЫХ ДЛЯ. ПОЛУЧЕНИЯ 
ТАБЛ.~6,---ПОСЛЕДОВАТЕЛЬНОСТИ $(2^k-(-1)^k)/3$, $(3^k-1)/2$ И ЧИСЛА фИБОНАЧЧИ.

мИНИМАЛЬНОЕ ЧИСЛО ПЕРЕМЕЩЕНИЙ 6600 НАБЛЮДАЕТСЯ ДЛЯ ШАГОВ ВИДА $2^k+1$, 
НО ВАЖНО ПОНИМАТЬ, ЧТО НАДО УЧИТЫВАТЬ НЕ ТОЛЬКО ЧИСЛО ПЕРЕМЕЩЕНИЙ, ХОТЯ 
ИМЕННО ОНО АСИМПТОТИЧЕСКИ ДОМИНИРУЕТ В ОБЩЕМ ВРЕМЕНИ РАБОТЫ. тАК КАК ВРЕМЯ 
РАБОТЫ ПРОГРАММЫ D РАВНО $9B+10NT+\cdots$ ЕДИНИЦ, ЯСНО, ЧТО ЭКОНОМИЯ 
ОДНОГО ПРОСМОТРА ПРИМЕРНО ЭКВИВАЛЕНТНА СОКРАЩЕНИЮ ЧИСЛА
ПЕРЕМЕЩЕНИЙ НА ${10\over9} N$; МЫ ГОТОВЫ ДОБАВИТЬ 1100 ПЕРЕМЕЩЕНИЙ,
ЕСЛИ ЗА СЧЕТ ЭТОГО УДАСТСЯ СЭКОНОМИТЬ ОДИН ПРОСМОТР. 
пОЭТОМУ ПРЕДСТАВЛЯЕТСЯ НЕРАЗУМНЫМ НАЧИНАТЬ С $h_t$, БОЛЬШЕГО, ЧЕМ, 
СКАЖЕМ, $N/3$, ПОСКОЛЬКУ БОЛЬШОЙ ШАГ НЕ УБАВИТ ЧИСЛА ПОСЛЕДУЮЩИХ 
ПЕРЕМЕЩЕНИЙ НАСТОЛЬКО, ЧТОБЫ ОПРАВДАТЬ ПЕРВЫЙ ПРОСМОТР.

бОЛЬШОЕ ЧИСЛО ЭКСПЕРИМЕНТОВ С АЛГОРИТМОМ D ПРОВЕЛИ дЖЕЙМС пЕТЕРСОН И 
дЭВИД~л.~рАССЕЛ В сТЭНФОРДСКОМ УНИВЕРСИТЕТЕ В 1971~Г. оНИ ОБНАРУЖИЛИ, ЧТО ДЛЯ 
СРЕДНЕГО ЧИСЛА ПЕРЕМЕЩЕНИЙ $B$ ХОРОШИМ
%%117
\picture{тАБЛИЦА 6.}
%%118
\bye