\input style
%%150
ДЛЯ СОРТИРОВКИ) БЫСТРАЯ СОРТИРОВКА ПРЕВРАЩАЕТСЯ В ОТНЮДЬ НЕ БЫСТРУЮ. вРЕМЯ 
ЕЕ РАБОТЫ СТАНОВИТСЯ ПРОПОРЦИОНАЛЬНЫМ 
$N^2$, А НЕ $N\log N$ (СМ. УПР.~25). в ОТЛИЧИЕ ОТ ДРУГИХ 
АЛГОРИТМОВ СОРТИРОВКИ, КОТОРЫЕ НАМ ВСТРЕЧАЛИСЬ, АЛГОРИТМ Q 
ПРЕДПОЧИТАЕТ НЕУПОРЯДОЧЕННЫЕ ФАЙЛЫ!

в УПОМЯНУТОЙ СТАТЬЕ хОАРА ПРЕДЛОЖЕНЫ ДВА СПОСОБА ПОПРАВИТЬ СИТУАЦИЮ, 
ОСНОВЫВАЮЩИХСЯ НА ВЫБОРЕ ЛУЧШЕГО ЗНАЧЕНИЯ ПРОВЕРЯЕМОГО КЛЮЧА $K$, КОТОРЫЙ 
УПРАВЛЯЕТ РАЗДЕЛЕНИЕМ. оДНА ИЗ ЕГО РЕКОМЕНДАЦИЙ СОСТОИТ .В ТОМ, ЧТОБЫ В 
ПОСЛЕДНЕЙ ЧАСТИ ШАГА Q2 ВЫБИРАТЬ \emph{СЛУЧАЙНОЕ} ЦЕЛОЕ ЧИСЛО $q$ МЕЖДУ 
$l$ И~$r$; В ЭТОМ ШАГЕ МОЖНО ЗАМЕНИТЬ ИНСТРУКЦИИ "$K\asg K_l$, $R\asg 
R_l$"  НА
$$
K\asg K_q, \quad R\asg R_q, \quad R_q\asg R_l.
\eqno(27)
$$
сОГЛАСНО ФОРМУЛАМ (25), ТАКИЕ СЛУЧАЙНЫЕ ЦЕЛЫЕ ЧИСЛА ПРИДЕТСЯ ВЫЧИСЛЯТЬ В 
СРЕДНЕМ ЛИШЬ $2(N+1)/(M+2)-1$~РАЗ, ТАК ЧТО ДОПОЛНИТЕЛЬНОЕ ВРЕМЯ РАБОТЫ 
НЕСУЩЕСТВЕННО, А СЛУЧАЙНЫЙ ВЫБОР---ХОРОШАЯ ЗАЩИТА ОТ ОПАСНОСТИ ОКАЗАТЬСЯ В 
НАИХУДШЕЙ СИТУАЦИИ.

вТОРОЕ ПРЕДЛОЖЕНИЕ хОАРА СОСТОИТ В ТОМ, ЧТОБЫ ПРОСМОТРЕТЬ НЕБОЛЬШОЙ 
УЧАСТОК ФАЙЛА И НАЙТИ МЕДИАНУ ДЛЯ ЭТОЙ СОВОКУПНОСТИ ДАННЫХ. тАКОМУ 
ПОДХОДУ ПОСЛЕДОВАЛ р. к. сИНГЛТОН [{\sl CACM\/}, {\bf 12} (1969), 
185--187], КОТОРЫЙ ПРЕДЛОЖИЛ В КАЧЕСТВЕ $K_q$  БРАТЬ МЕДИАНУ ТРЕХ ЗНАЧЕНИЙ
$$
K_l, \quad K_{\lfloor(l+r)/2\rfloor}, \quad K_r.
\eqno(28)
$$

пРОЦЕДУРА сИНГЛТОНА СОКРАЩАЕТ ЧИСЛО СРАВНЕНИЙ С $2N \ln N$ ПРИМЕРНО 
ДО ${12\over7}N\ln N$ (СМ. УПР. 29). мОЖНО ПОКАЗАТЬ, ЧТО. В ЭТОМ
СЛУЧАЕ $B_N$ АСИМПТОТИЧЕСКИ ПРИБЛИЖАЕТСЯ К $C_N/5$, А НЕ К~$C_N/6$, ТАК 
ЧТО МЕТОД МЕДИАНЫ НЕСКОЛЬКО УВЕЛИЧИВАЕТ ВРЕМЯ, ЗАТРАЧИВАЕМОЕ НА 
ПЕРЕСЫЛКУ ДАННЫХ, ПОЭТОМУ ОБЩЕЕ ВРЕМЯ РАБОТЫ СОКРАЩАЕТСЯ ПРИМЕРНО, НА 
8\%. (пОДРОБНЫЙ АНАЛИЗ СМ. В УПР.56.) вРЕМЯ РАБОТЫ В НАИХУДШЕМ СЛУЧАЕ ВСЕ 
ЕЩЕ ПОРЯДКА $N^2$, ОДНАКО С ТАКИМ МЕДЛЕННЫМ ПОВЕДЕНИЕМ АЛГОРИТМА ВРЯД ЛИ 
КОГДА-ЛИБО ПРИДЕТСЯ ВСТРЕТИТЬСЯ НА ПРАКТИКЕ.

у.~д.~фРЭЙЗЕР И а.~ч.~мАК-кЕЛЛАР 
[{\sl JACM\/}, {\bf 17} (1970), 496--507] 
ПРЕДЛОЖИЛИ РАССМАТРИВАТЬ СОВОКУПНОСТЬ ГОРАЗДО БОЛЬШЕГО ОБЎЕМА ИЗ $2^k-1$ 
ЗАПИСЕЙ, ГДЕ $k$ ВЫБИРАЕТСЯ ТАК, ЧТОБЫ $2^k\approx N/\ln N$. эТУ 
СОВОКУПНОСТЬ МОЖНО ОТСОРТИРОВАТЬ ОБЫЧНЫМ МЕТОДОМ БЫСТРОЙ СОРТИРОВКИ, ПОСЛЕ 
ЧЕГО ЭЛЕМЕНТЫ ВСТАВЛЯЮТСЯ СРЕДИ ОСТАЛЬНЫХ ЗАПИСЕЙ ЗА $k$ ПРОСМОТРОВ ВСЕГО 
ФАЙЛА (В РЕЗУЛЬТАТЕ ФАЙЛ БУДЕТ РАЗДЕЛЕН НА $2^k$ ПОДФАЙЛОВ, ОГРАНИЧЕННЫХ 
ЭЛЕМЕНТАМИ ПЕРВОНАЧАЛЬНОЙ СОВОКУПНОСТИ). нА ЗАКЛЮЧИТЕЛЬНОМ 
ЭТАПЕ СОРТИРУЮТСЯ ПОЛУЧЕННЫЕ ПОДФАЙЛЫ. сРЕДНЕЕ ЧИСЛО, СРАВНЕНИЙ,
 ВЫПОЛНЯЕМЫХ ТАКОЙ ПРОЦЕДУРОЙ "СОРТИРОВКИ СОВОКУПНОСТИ", ПРИМЕРНО ТАКОЕ 
ЖЕ, КАК И ДЛЯ МЕТОДА МЕДИАНЫ сИНГЛТОНА, КОГДА $N$
%%151
НАХОДИТСЯ В ПРАКТИЧЕСКОМ ДИАПАЗОНЕ ЗНАЧЕНИЙ, НО ПРИ $N\to\infty$ ОНО 
АСИМПТОТИЧЕСКИ ПРИБЛИЖАЕТСЯ К $N\log_2N$.

\section оБМЕННАЯ ПОРАЗРЯДНАЯ СОРТИРОВКА. мЫ ПОДХОДИМ ТЕПЕРЬ К МЕТОДУ,
 СОВЕРШЕННО ОТЛИЧНОМУ ОТ ВСЕХ СХЕМ СОРТИРОВКИ, КОТОРЫЕ РАССМАТРИВАЛИСЬ 
ПРЕЖДЕ; В НЕМ ИСПОЛЬЗУЕТСЯ \emph{ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ} КЛЮЧЕЙ, 
И.ПОТОМУ ОН ПРЕДНАЗНАЧЕН ИСКЛЮЧИТЕЛЬНО ДЛЯ ДВОИЧНЫХ МАШИН. вМЕСТО ТОГО 
ЧТОБЫ СРАВНИВАТЬ МЕЖДУ СОБОЙ ДВА КЛЮЧА, В ЭТОМ МЕТОДЕ ПРОВЕРЯЕТСЯ, РАВНЫ 
ЛИ 0 ИЛИ 1 ОТДЕЛЬНЫЕ БИТЫ КЛЮЧА. в ДРУГИХ ОТНОШЕНИЯХ ОН ОБЛАДАЕТ 
ХАРАКТЕРИСТИКАМИ ОБМЕННОЙ СОРТИРОВКИ И НА САМОМ ДЕЛЕ ОЧЕНЬ НАПОМИНАЕТ 
БЫСТРУЮ СОРТИРОВКУ. тАК КАК ОН ЗАВИСИТ ОТ РАЗРЯДОВ КЛЮЧА, 
ПРЕДСТАВЛЕННОГО В ДВОИЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ, МЫ НАЗЫВАЕМ ЕГО 
"ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКОЙ". в ОБЩИХ ЧЕРТАХ ЭТОТ АЛГОРИТМ МОЖНО 
ОПИСАТЬ СЛЕДУЮЩИМ ОБРАЗОМ:
\enumerate
\li пОСЛЕДОВАТЕЛЬНОСТЬ СОРТИРУЕТСЯ \emph{ПО СТАРШЕМУ ЗНАЧАЩЕМУ ДВОИЧНОМУ 
БИТУ} ТАК, ЧТОБЫ ВСЕ КЛЮЧИ, НАЧИНАЮЩИЕСЯ С 0, ОКАЗАЛИСЬ ПЕРЕД ВСЕМИ 
КЛЮЧАМИ, НАЧИНАЮЩИМИСЯ С 1. дЛЯ ЭТОГО НАДО НАЙТИ САМЫЙ ЛЕВЫЙ КЛЮЧ $K_i$, 
НАЧИНАЮЩИЙСЯ С 1, И САМЫЙ ПРАВЫЙ КЛЮЧ $K_j$, НАЧИНАЮЩИЙСЯ С 0, ПОСЛЕ ЧЕГО 
$R_i$ И $R_j$ МЕНЯЮТСЯ МЕСТАМИ, И ПРОЦЕСС  ПОВТОРЯЕТСЯ, ПОКА НЕ СТАНЕТ $i>j$.

\li пУСТЬ $F_0$---МНОЖЕСТВО ЭЛЕМЕНТОВ, НАЧИНАЮЩИХСЯ С 0, А $F_1$---ВСЕ 
ОСТАЛЬНЫЕ. пРИМЕНИМ К $F_0$ ПОРАЗРЯДНУЮ СОРТИРОВКУ (НАЧАВ ТЕПЕРЬ СО 
\emph{ВТОРОГО} БИТА СЛЕВА, А НЕ СО СТАРШЕГО) ДО ТЕХ ПОР, ПОКА МНОЖЕСТВО 
$F_0$ .НЕ БУДЕТ ПОЛНОСТЬЮ ОТСОРТИРОВАНО; ЗАТЕМ ПРОДЕЛАЕМ ТО ЖЕ С $F_1$.
\enumend

нАПРИМЕР, В ТАБЛ.~3 ПОКАЗАНО, КАК ДЕЙСТВУЕТ ОБМЕННАЯ ПОРАЗРЯДНАЯ 
СОРТИРОВКА НА НАШИ 16 СЛУЧАЙНЫХ ЧИСЕЛ, ЗАПИСАННЫХ ТЕПЕРЬ В ВОСЬМЕРИЧНОЙ 
СИСТЕМЕ СЧИСЛЕНИЯ. нА СТАДИИ 1 ПОКАЗАН ИСХОДНЫЙ ФАЙЛ; ПОСЛЕ ОБМЕНОВ ПО 
ПЕРВОМУ БИТУ ПРИХОДИМ КО ВТОРОЙ СТАДИИ. нА ВТОРОЙ СТАДИИ СОРТИРУЕТСЯ 
ПЕРВАЯ ГРУППА ПО ВТОРОМУ, БИТУ, НА ТРЕТЬЕЙ---ПО ТРЕТЬЕМУ БИТУ. (чИТАТЕЛЬ 
ДОЛЖЕН МЫСЛЕННО ПРЕОБРАЗОВАТЬ ВОСЬМЕРИЧНЫЕ ЧИСЛА В 10-РАЗРЯДНЫЕ 
ДВОИЧНЫЕ.) кОГДА МЫ ПОСЛЕ СОРТИРОВКИ ПО .ЧЕТВЕРТОМУ БИТУ ДОСТИГАЕМ ПЯТОЙ 
СТАДИИ, ТО ОБНАРУЖИВАЕМ, ЧТО КАЖДАЯ ИЗ ОСТАВШИХСЯ ГРУПП СОДЕРЖИТ ВСЕГО 
ПО ОДНОМУ ЭЛЕМЕНТУ,- ТАК ЧТО ЭТУ ЧАСТЬ ФАЙЛА МОЖНО БОЛЬШЕ  НЕ  
РАССМАТРИВАТЬ. зАПИСЬ "${}^4[0232\ 0252]$" ОЗНАЧАЕТ, ЧТО ПОДФАЙЛ $0232\ 
0252$ ЕЩЕ ПРЕДСТОИТ СОРТИРОВАТЬ ПО ЧЕТВЕРТОМУ БИТУ СЛЕВА. в ЭТОМ 
КОНКРЕТНОМ СЛУЧАЕ СОРТИРОВКА ПО ЧЕТВЕРТОМУ БИТУ НЕ ДАЕТ НИЧЕГО НОВОГО; 
ЧТОБЫ РАЗДЕЛИТЬ ЭЛЕМЕНТЫ, НЕОБХОДИМО ДОБРАТЬСЯ ДО ПЯТОГО БИТА.

вЕСЬ ПРОЦЕСС СОРТИРОВКИ, ПОКАЗАННЫЙ В ТАБЛ.~3, ВЫПОЛНЯЕТСЯ ЗА 22 СТАДИИ; 
ЭТО НЕСКОЛЬКО БОЛЬШЕ СООТВЕТСТВУЮЩЕГО ЧИСЛА В БЫСТРОЙ СОРТИРОВКЕ (ТАБЛ.~2).
 чИСЛО ПРОВЕРОК БИТОВ 82 ТАКЖЕ ВЕЛИКО; НО МЫ УВИДИМ, ЧТО ЧИСЛО ПРОВЕРОК 
БИТОВ ПРИ БОЛЬШИХ
151
%%152
\picture{тАБЛИЦА 3}
%%153
$N$ В ДЕЙСТВИТЕЛЬНОСТИ МЕНЬШЕ, ЧЕМ ЧИСЛО СРАВНЕНИЙ В БЫСТРОЙ СОРТИРОВКЕ, В 
ПРЕДПОЛОЖЕНИИ О РАВНОМЕРНОМ РАСПРЕДЕЛЕНИИ КЛЮЧЕЙ. оБЩЕЕ ЧИСЛО ОБМЕНОВ В 
ТАБЛ.~3 РАВНО 17, Т. Е. ВЕСЬМА УМЕРЕННО. зАМЕТИМ, ЧТО, ХОТЯ СОРТИРУЮТСЯ 
10-БИТОВЫЕ ЧИСЛА, В ДАННОМ ПРИМЕРЕ ПРИ ПРОВЕРКЕ БИТОВ НИКОГДА НЕ 
ПРИХОДИТСЯ ИДТИ ДАЛЬШЕ СЕДЬМОГО БИТА.

кАК И ПРИ БЫСТРОЙ СОРТИРОВКЕ, ДЛЯ ХРАНЕНИЯ "ИНФОРМАЦИИ О ГРАНИЦАХ" 
ПОДФАЙЛОВ, ОЖИДАЮЩИХ СОРТИРОВКИ, МОЖНО ВОСПОЛЬЗОВАТЬСЯ СТЕКОМ. вМЕСТО 
ТОГО ЧТОБЫ СОРТИРОВАТЬ В ПЕРВУЮ ОЧЕРЕДЬ НАИМЕНЬШИЙ ИЗ ПОДФАЙЛОВ, УДОБНО 
ПРОСТО ПРОДВИГАТЬСЯ СЛЕВА НАПРАВО, ТАК КАК РАЗМЕР СТЕКА В. ЭТОМ СЛУЧАЕ 
НИКОГДА НЕ ПРЕВЗОЙДЕТ ЧИСЛА БИТОВ В СОРТИРУЕМЫХ КЛЮЧАХ. в АЛГОРИТМЕ, 
ПРИВЕДЕННОМ НИЖЕ, ЭЛЕМЕНТ СТЕКА $(r, b)$ УКАЗЫВАЕТ НА ТО, ЧТО ПОДФАЙЛ С 
ПРАВОЙ ГРАНИЦЕЙ $r$ ОЖИДАЕТ СОРТИРОВКИ ПО БИТУ $b$; ЛЕВУЮ ГРАНИЦУ МОЖНО 
НЕ ЗАПОМИНАТЬ В СТЕКЕ: ОНА ВСЕГДА ЗАДАНА НЕЯВНО, ПОСКОЛЬКУ В ЭТОЙ 
ПРОЦЕДУРЕ ФАЙЛ ВСЕГДА ОБРАБАТЫВАЕТСЯ СЛЕВА НАПРАВО.

\alg R.(оБМЕННАЯ ПОРАЗРЯДНАЯ СОРТИРОВКА.) зАПИСИ $R_1$, \dots, $R_N$ 
ПЕРЕРАЗМЕЩАЮТСЯ НА ТОМ ЖЕ МЕСТЕ; ПОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ ИХ КЛЮЧИ 
БУДУТ УПОРЯДОЧЕНЫ: $K_1\le \ldots \le K_N$. пРЕДПОЛАГАЕТСЯ, ЧТО ВСЕ 
КЛЮЧИ---$m$-РАЗРЯДНЫЕ ДВОИЧНЫЕ ЧИСЛА $(a_1\ a_2\ \ldots\ a_m)_2$; $i$-Й ПО 
СТАРШИНСТВУ БИТ $a_i$ НАЗЫВАЕТСЯ 
"БИТ $i$" КЛЮЧА. тРЕБУЕТСЯ ВСПОМОГАТЕЛЬНЫЙ СТЕК, ВМЕЩАЮЩИЙ ДО 
$m-1$ ЭЛЕМЕНТОВ. эТОТ АЛГОРИТМ, ПО СУЩЕСТВУ, СЛЕДУЕТ ПРОЦЕДУРЕ ОБМЕННОЙ 
ПОРАЗРЯДНОЙ СОРТИРОВКИ С РАЗДЕЛЕНИЯМИ, ОПИСАННОЙ ВЫШЕ;
ВОЗМОЖНЫ НЕКОТОРЫЕ УСОВЕРШЕНСТВОВАНИЯ С ЦЕЛЬЮ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ (ОНИ 
ОПИСАНЫ ДАЛЕЕ В ТЕКСТЕ И В УПРАЖНЕНИЯХ).

\st[нАЧАЛЬНАЯ УСТАНОВКА.] оПУСТОШИТЬ СТЕК И УСТАНОВИТЬ $l\asg 1$, $r\asg 
N$, $b\asg 1$.

\st[нАЧАТЬ НОВУЮ СТАДИЮ.] (мЫ ХОТЕЛИ БЫ ТЕПЕРЬ ОТСОРТИРОВАТЬ ПОДФАЙЛ  
$R_l\le \ldots \le R_r$ ПО БИТУ $b$; ПО СМЫСЛУ АЛГОРИТМА $l\le r$.) еСЛИ 
$l=r$, ТО ПЕРЕЙТИ К ШАГУ \stp{10} (ТАК КАК ФАЙЛ, СОСТОЯЩИЙ ИЗ ОДНОГО СЛОВА,
 УЖЕ ОТСОРТИРОВАН). в ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ $i\asg l$, $j\asg r$.

\st[пРОВЕРИТЬ $K_i$ НА 1.] пРОВЕРИТЬ БИТ $b$ КЛЮЧА $K_i$.. еСЛИ ОН РАВЕН 1,
 ТО ПЕРЕЙТИ К ШАГУ \stp{6}.

\st[уВЕЛИЧИТЬ $i$.] уВЕЛИЧИТЬ $i$ НА 1. еСЛИ $i\le j$, ТО ВОЗВРАТИТЬСЯ К 
ШАГУ \stp{3}; В ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ К ШАГУ \stp{8}.

\st[пРОВЕРИТЬ $K_{j+1}$ НА 0.] пРОВЕРИТЬ БИТ $b$ КЛЮЧА $K_{j+1}$. еСЛИ ОН 
РАВЕН 0, ТО ПЕРЕЙТИ К ШАГУ \stp{7}.

\st[уМЕНЬШИТЬ $j$.] уМЕНЬШИТЬ $j$ НА 1. еСЛИ$ i\le j$, ТО ПЕРЕЙТИ К ШАГУ 
\stp{5}; В ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ К ШАГУ \stp{8}.

\st[пОМЕНЯТЬ МЕСТАМИ $R_i$, $R_{j+1}$]. пОМЕНЯТЬ МЕСТАМИ 
$R_i\xchg R_{j+1}$, ЗАТЕМ ПЕРЕЙТИ К ШАГУ \stp{4}.

\st[пРОВЕРИТЬ ОСОБЫЕ СЛУЧАИ.] (к ЭТОМУ МОМЕНТУ СТАДИЯ РАЗДЕЛЕНИЯ
%%154
ЗАВЕРШЕНА, $i=j+1$, БИТ $b$ КЛЮЧЕЙ~$K_l$, \dots, $K_j$  РАВЕН~$0$, 
А БИТ~$b$ КЛЮЧЕЙ $K_i$, \dots, $K_r$ РАВЕН~$1$.) уВЕЛИЧИТЬ $b$ НА~1. еСЛИ 
$b>m$, ГДЕ $m$---ОБЩЕЕ ЧИСЛО БИТОВ В КЛЮЧАХ, ТО ПЕРЕЙТИ К ШАГУ~\stp{10}. 
(эТО ОЗНАЧАЕТ, ЧТО ПОДФАЙЛ $R_l$ \dots $R_r$ ОТСОРТИРОВАН. еСЛИ В ФАЙЛЕ НЕ 
МОЖЕТ БЫТЬ РАВНЫХ КЛЮЧЕЙ, ТО ТАКУЮ ПРОВЕРКУ МОЖНО НЕ ДЕЛАТЬ.) в ПРОТИВНОМ 
СЛУЧАЕ, ЕСЛИ~$j<l$ ИЛИ~$j=r$, ВОЗВРАТИТЬСЯ К ШАГУ~\stp{2} (ВСЕ 
ПРОСМОТРЕННЫЕ БИТЫ ОКАЗАЛИСЬ РАВНЫМИ СООТВЕТСТВЕННО~1 ИЛИ~0). еСЛИ ЖЕ 
$j=l$, ТО УВЕЛИЧИТЬ $l$ НА~1 И ПЕРЕЙТИ К ШАГУ~\stp{2} (ВСТРЕТИЛСЯ ТОЛЬКО 
ОДИН БИТ, РАВНЫЙ 0).

\st[пОМЕСТИТЬ В СТЕК.] пОМЕСТИТЬ В СТЕК ЭЛЕМЕНТ $(r, b)$, ЗАТЕМ УСТАНОВИТЬ 
$r\asg j$ И ПЕРЕЙТИ К ШАГУ \stp{2}.

\st[вЗЯТЬ ИЗ СТЕКА.] еСЛИ СТЕК ПУСТ, ТО СОРТИРОВКА ЗАКОНЧЕНА. в 
ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ $l\asg r+1$, ВЗЯТЬ ИЗ. СТЕКА ЭЛЕМЕНТ $(r', 
b')$, УСТАНОВИТЬ $r\asg r'$, $b\asg b'$ И ВОЗВРАТИТЬСЯ К ШАГУ~\stp{2}.
\algend

\prog R.(оБМЕННАЯ ПОРАЗРЯДНАЯ СОРТИРОВКА.) в СЛЕДУЮЩЕЙ ПРОГРАММЕ ДЛЯ 
МАШИНЫ \MIX{} ИСПОЛЬЗУЮТСЯ, ПО СУЩЕСТВУ, ТЕ ЖЕ СОГЛАШЕНИЯ, ЧТО И В 
ПРОГРАММЕ Q. зНАЧЕНИЯ РЕГИСТРОВ: $|rI1|\equiv l-r$, $|rI2|\equiv r$, 
$|rI3|\equiv i$, $|rI4|=j$, $|rI5|\equiv m-b$,  
$|rI6|=\hbox{РАЗМЕР СТЕКА}$, ЕСЛИ НЕ СЧИТАТЬ ТОГО, ЧТО В НЕКОТОРЫХ 
КОМАНДАХ (ОТМЕЧЕННЫХ НИЖЕ) УДОБНО ОСТАВИТЬ~$|rI3|=i-j$ ИЛИ~$|rI4|=j-i$. 
дВОИЧНОЙ ПРИРОДОЙ ПОРАЗРЯДНОЙ СОРТИРОВКИ ОБЎЯСНЯЕТСЯ ИСПОЛЬЗОВАНИЕ В ЭТОЙ 
ПРОГРАММЕ КОМАНД |SRB| (ДВОИЧНЫЙ СДВИГ СОДЕРЖИМОГО |AX| ВПРАВО), |JAE| 
(ПЕРЕХОД, ЕСЛИ СОДЕРЖИМОЕ |A| ЧЕТНО) И |JAO| (ПЕРЕХОД, ЕСЛИ СОДЕРЖИМОЕ |A| 
НЕЧЕТНО), ОПРЕДЕЛЕННЫХ В П.~4.5.2. пРЕДПОЛАГАЕТСЯ, ЧТО $N\ge 2$.
\code
START& ENT6 & 0         & 1 & R1. нАЧАЛЬНАЯ УСТАНОВКА. оПУСТОШИТЬ СТЕК.
     & ENT1 &1-N        & 1 & $l\asg 1$.
     & ENT2 &N          & 1 & $r\asg N$.
     & ENT5 &м-1        & 1 & $b\asg 1$.
     & JMP  &1F         & 1 & к R2 (ОПУСТИТЬ ПРОВЕРКУ $l=r$).
9H   & INC6 &1          & S & R9. пОМЕСТИТЬ В СТЕК. [$|rI4|=l-j$]
     & ST2  &STACK,6(A) & S
     & ST5  &STACK,6(в) & S & $(r, b)\Rightarrow\hbox{СТЕК}$.
     & ENN1 &0,4        & S & $|rI1|\asg l-j$.
     & ENT2 &-1,3       & S & $r\asg j$.
1H   & ENT3 &0,1        & а & R2. нАЧАТЬ НОВУЮ СТАДИЮ. [$|rI3|=i-j$]
     & ENT4 &0,2        & A & $i\asg l$, $j\asg r$. [$|rI3|=i-j$]
3H   & INC3 &0,4        & C'& R3. пРОВЕРИТЬ $K_i$ НА 1.
     & LDA  &INPUT,3    & C'&
     & SRB  &0,5        & C'& $\hbox{МЛАДШИЙ БИТ |rA|}\asg\hbox{БИТ $b$ КЛЮЧА $K_i$}$.
%%155
       &JAE   &4F       & C'   & к R4, ЕСЛИ ОН РАВЕН 0.
6н     &DEC4  &1,3      & C''+X& R6. уМЕНЬШИТЬ $j\asg j-l$. [$|rI4|=j-i$].
       &J4N   &8F       & C''+X& к R8, ЕСЛИ $j<i$. [$|rI4|=j-i$]
5н     &INC4  &0,3      & C''  & R5. пРОВЕРИТЬ $K_{j+1}$ НА $0$.
       &LDA   &INPUT+1,4& C''
       &SRB   &0,5      & C''  & $\hbox{МЛАДШИЙ БИТ |rA|}\asg\hbox{БИТ $b$ КЛЮЧА $K_{j+1}$.}$
       &JAO   &6в       & C''  & к R6, ЕСЛИ ОН РАВЕН 1.
7н     &LDA   &INPUT+1,4& B    & R7. пОМЕНЯТЬ МЕСТАМИ $R_i$, $R_{j+1}$.
       &LDX   &INPUT,3  & B
       &STX   &INPUT+1,4& B
       &STA   &INPUT,3  & B
4H     &DEC3  &-1,4     & C'-X  & R4. уВЕЛИЧИТЬ $i$. $i\asg i+1$. [$|rI3|=i-j$]
       &J3NP  &3B       &C'-X    & к R3, ЕСЛИ $i\le j$. [$|rI3|=i-j$]
       &INC3  &0,4      &A-X     & $|rI3|\asg i$.
8н     &J5Z   &0F       &A       & R8.  пРОВЕРИТЬ ОСОБЫЕ СЛУЧАИ. [$|rI4|=\hbox{НЕИЗВЕСТЕН}$]
       &DEC5  &1        &A-G     & к R10, ЕСЛИ $b=m$, ИНАЧЕ $b\asg b-1$.
       &ENT4  &-1,3     &A-G     &$|rI4|\asg j$.
       &DEC4  &0,2      &A-G     &$|rI4|\asg j-r$.
       &J4Z   &1в       &A-G     & к R2, ЕСЛИ $j=r$.
       &DEC4  &0,1      &A-G-R   &$|rI4|\asg j-l$.
       &J4N   &1в       &A-G-R   & к R2, ЕСЛИ $j<l$.
       &J4NZ  &9в       &A-G-L-R & к R9, ЕСЛИ $j\ne l$.
       &INC1  &1        & K      & $l\asg l+1$.
2н     &J1NZ  &1в       & K+S    & пЕРЕХОД, ЕСЛИ $l\ne r$.
0н     &ENT1  &1,2      & S+1    & R10. вЗЯТЬ ИЗ СТЕКА.
       &LD2   &STACK, 6 (A)& S+1
       &DEC1  &0,2      & S+1
       &LD5   &STACK,6 (в)& S+1  & $\hbox{сТЕК}\Rightarrow(r, b)$
       &DEC6  &1        & S+1
       &J6NN  &2в       & S+1    & к R2, ЕСЛИ СТЕК НЕ БЫЛ ПУСТ.
\endcode
\progend

вРЕМЯ РАБОТЫ ПРОГРАММЫ ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКИ ЗАВИСИТ ОТ
$$
\eqalign{
A &=\hbox{ЧИСЛО СТАДИЙ, В КОТОРЫХ $l<r$;}\cr
B &=\hbox{ЧИСЛО ЗАМЕЩЕНИЙ;}\cr
C &=C'+C''=\hbox{ЧИСЛО ПРОВЕРОК БИТОВ;}\cr
G&=\hbox{ЧИСЛО СЛУЧАЕВ, КОГДА В ШАГЕ R8 $b>m$;}\cr
K&=\hbox{ЧИСЛО СЛУЧАЕВ, КОГДА В ШАГЕ R8 $b\le m$, $j=l$;}\cr
L&=\hbox{ЧИСЛО СЛУЧАЕВ, КОГДА В ШАГЕ R8 $b\le m$, $j<l$;}\cr
R&=\hbox{ЧИСЛО СЛУЧАЕВ, КОГДА В ШАГЕ R8 $b\le m$, $j=r$;}\cr
S&=\hbox{ЧИСЛО СЛУЧАЕВ, КОГДА ЧТО-ЛИБО ПОМЕЩАЕТСЯ В СТЕК;}\cr
X&=\hbox{ЧИСЛО СЛУЧАЕВ, КОГДА В ШАГЕ R6 $j<i$.}\cr
}
\eqno(29)
$$
%% 156
пО ЗАКОНУ кИРХГОФА $S=A-G-K-L-R$, ТАК ЧТО ОБЩЕЕ ВРЕМЯ ВЫПОЛНЕНИЯ  РАВНО 
$27A+8B+8C-23G-14K-17L-19R-X+13$ ЕДИНИЦ. зА СЧЕТ УСЛОЖНЕНИЯ ПРОГРАММЫ 
МОЖНО НЕСКОЛЬКО УСКОРИТЬ ЦИКЛЫ ПРОВЕРКИ БИТОВ (СМ. УПР.~34). оБМЕННУЮ 
ПОРАЗРЯДНУЮ СОРТИРОВКУ МОЖНО ТАКЖЕ УСКОРИТЬ, ЕСЛИ ПРИ ДОСТАТОЧНО МАЛЫХ 
ЗНАЧЕНИЯХ РАЗНОСТИ $r-l$ ПРИМЕНЯТЬ ПРОСТЫЕ ВСТАВКИ, КАК ЭТО СДЕЛАНО В 
АЛГОРИТМЕ Q, НО МЫ НЕ БУДЕМ ЗАДЕРЖИВАТЬСЯ НА ТАКИХ УСОВЕРШЕНСТВОВАНИЯХ.

дЛЯ АНАЛИЗА ВРЕМЕНИ ВЫПОЛНЕНИЯ ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКИ 
НАПРАШИВАЮТСЯ ДВА ТИПА ИСХОДНЫХ ДАННЫХ:
\medskip
\item{i)} пУСТЬ $N=2^m$ И КЛЮЧИ, КОТОРЫЕ НАДО ОТСОРТИРОВАТЬ,--- ПРОСТО ЧИСЛА 
$0$, $1$, $2$, \dots, $2^m-1$, РАСПОЛОЖЕННЫЕ В СЛУЧАЙНОМ ПОРЯДКЕ.

\item{ii)} пУСТЬ $m=\infty$ (НЕОГРАНИЧЕННАЯ ТОЧНОСТЬ) И КЛЮЧИ, 
КОТОРЫЕ НАДО ОТСОРТИРОВАТЬ,---НЕЗАВИСИМЫЕ, РАВНОМЕРНО РАСПРЕДЕЛЕННЫЕ В 
ПРОМЕЖУТКЕ $[0, 1)$ ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА.
\medskip
\noindent
аНАЛИЗ СЛУЧАЯ~(i) ОТНОСИТЕЛЬНО ПРОСТ, ПОЭТОМУ ОН ОСТАВЛЕН ЧИТАТЕЛЮ В 
КАЧЕСТВЕ УПРАЖНЕНИЯ (СМ. УПР.~35). сЛУЧАЙ~(ii) СРАВНИТЕЛЬНО СЛОЖЕН, 
ПОЭТОМУ ОН \emph{ТАКЖЕ} ОСТАВЛЕН ДЛЯ УПРАЖНЕНИЙ. в СЛЕДУЮЩЕЙ ТАБЛИЦЕ 
ПРИВЕДЕНЫ ГРУБЫЕ ОЦЕНКИ РЕЗУЛЬТАТОВ ТОГО И ДРУГОГО АНАЛИЗОВ:
$$
\matrix{
\hbox{\bf вЕЛИЧИНА} & \hbox{\bf сЛУЧАЙ (i)} & \hbox{\bf сЛУЧАЙ (ii)}\cr
A & N & \alpha N\cr
B & {1\over4} N\log_2N & {1\over4}N\log_2 N\cr
C &  N\log_2N & N\log_2N \cr
G &{1\over2} N & 0 \cr
K & 0 & {1\over2} N\cr
L & 0 &  {1\over2} (\alpha-1)N\cr
R & 0 &  {1\over2} (\alpha-1)N\cr
S & {1\over2}N & {1\over2}N\cr
X & {1\over2}N & {1\over4} (\alpha-1)N\cr
}
\eqno(30)
$$
зДЕСЬ $\alpha=1/(\ln 2)=1.4427$. зАМЕТИМ, ЧТО СРЕДНЕЕ ЧИСЛО ОБМЕНОВ,
 ПРОВЕРОК БИТОВ И ОБРАЩЕНИЙ К СТЕКУ, ПО СУЩЕСТВУ, ОДИНАКОВО В ОБОИХ 
СЛУЧАЯХ, НЕСМОТРЯ ДАЖЕ НА ТО, ЧТО В СЛУЧАЕ (ii) ЧИСЛО СТАДИЙ НА 44\% 
БОЛЬШЕ. нА СОРТИРОВКУ $N$ ЭЛЕМЕНТОВ В СЛУЧАЕ (ii) НАША \MIX-ПРОГРАММА 
ЗАТРАТИТ В СРЕДНЕМ ПРИБЛИЗИТЕЛЬНО $14.4N\ln N$ ЕДИНИЦ ВРЕМЕНИ. эТО ЧИСЛО 
МОЖНО БЫЛО БЫ СОКРАТИТЬ ПРИМЕРНО ДО $11.5N\ln N$, ЕСЛИ ВОСПОЛЬЗОВАТЬСЯ 
ПРЕДЛОЖЕНИЕМ ИЗ УПР.~34. сООТВЕТСТВУЮЩАЯ ВЕЛИЧИНА ДЛЯ ПРОГРАММЫ Q РАВНА
%% 157
$12.7N \ln N$, НО И ЕЕ МОЖНО УМЕНЬШИТЬ ДО~$11.7 N \ln N$, ЕСЛИ 
ВОСПОЛЬЗОВАТЬСЯ ПРЕДЛОЖЕНИЕМ сИНГЛТОНА И ВЫБИРАТЬ МЕДИАНУ ИЗ ТРЕХ КЛЮЧЕЙ.

в СЛУЧАЕ РАВНОМЕРНОГО РАСПРЕДЕЛЕНИЯ ДАННЫХ ОБМЕННАЯ ПОРАЗРЯДНАЯ 
СОРТИРОВКА ЗАНИМАЕТ В СРЕДНЕМ ПРИМЕРНО СТОЛЬКО ЖЕ ВРЕМЕНИ, СКОЛЬКО И 
БЫСТРАЯ СОРТИРОВКА; ФАКТИЧЕСКИ ДЛЯ МАШИНЫ \MIX{} ОНА НЕМНОГО БЫСТРЕЕ, ЧЕМ 
БЫСТРАЯ СОРТИРОВКА. в УПР.~53 ПОКАЗАНО, В КАКОЙ МЕРЕ ЗАМЕДЛЯЕТСЯ ЭТОТ 
ПРОЦЕСС ПРИ НЕРАВНОМЕРНОМ РАСПРЕДЕЛЕНИИ. вАЖНО ОТМЕТИТЬ, ЧТО ВЕСЬ НАШ 
АНАЛИЗ ОСНОВАН НА ПРЕДПОЛОЖЕНИИ О ТОМ. ЧТО ВСЕ КЛЮЧИ РАЗЛИЧНЫ. 
\emph{06МЕННАЯ ПОРАЗРЯДНАЯ СОРТИРОВКА В ТОМ ВИДЕ, КАК ОНА ОПИСАНА ВЫШЕ, НЕ 
ОЧЕНЬ ЭФФЕКТИВНА, ЕСЛИ ИМЕЮТСЯ ОДИНАКОВЫЕ КЛЮЧИ,} ТАК КАК ОНА ПРОХОДИТ 
ЧЕРЕЗ НЕСКОЛЬКО СТАДИЙ, ТРЕБУЮЩИХ ВРЕМЕНИ, ПЫТАЯСЬ РАЗДЕЛИТЬ МНОЖЕСТВА 
ОДИНАКОВЫХ КЛЮЧЕЙ, ПОКА $b$ НЕ СТАНЕТ $>m$. оДИН ПРИЕМЛЕМЫЙ СПОСОБ 
ИСПРАВИТЬ ЭТОТ НЕДОСТАТОК ПРЕДЛОЖЕН В ОТВЕТЕ К УПР.~40.

кАК ОБМЕННАЯ ПОРАЗРЯДНАЯ СОРТИРОВКА, ТАК И БЫСТРАЯ СОРТИРОВКА ОСНОВАНЫ 
НА ИДЕЕ РАЗДЕЛЕНИЯ. зАПИСИ МЕНЯЮТСЯ МЕСТАМИ ДО ТЕХ ПОР, ПОКА ФАЙЛ НЕ БУДЕТ 
РАЗБИТ НА ДВЕ ЧАСТИ: ЛЕВЫЙ ПОДФАЙЛ, В КОТОРОМ ВСЕ КЛЮЧИ $\le K$ ПРИ 
НЕКОТОРОМ $K$, И ПРАВЫЙ ПОДФАЙЛ, В КОТОРОМ ВСЕ КЛЮЧИ $\ge K$. в БЫСТРОЙ 
СОРТИРОВКЕ В КАЧЕСТВЕ $K$ ВЫБИРАЕТСЯ РЕАЛЬНЫЙ КЛЮЧ ИЗ ФАЙЛА, В ТО ВРЕМЯ 
КАК В ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКЕ, ПО СУЩЕСТВУ, ВЫБИРАЕТСЯ НЕКОТОРЫЙ 
ИСКУССТВЕННЫЙ КЛЮЧ НА ОСНОВЕ ДВОИЧНЫХ ПРЕДСТАВЛЕНИЙ. чТО КАСАЕТСЯ 
ИСТОРИЧЕСКОЙ СТОРОНЫ ДЕЛА, ТО ОБМЕННУЮ ПОРАЗРЯДНУЮ СОРТИРОВКУ ОТКРЫЛИ 
п.~хИЛЬДЕБРАНДТ, г.~иСБИТЦ, X.~рАЙЗИНГ И ж.~шВАРЦ [{\sl JACM\/}, {\bf 6} 
(1959), 156--163] ПРИМЕРНО ЗА ГОД ДО ИЗОБРЕТЕНИЯ БЫСТРОЙ СОРТИРОВКИ. 
вОЗМОЖНЫ ТАКЖЕ И ДРУГИЕ СХЕМЫ РАЗДЕЛЕНИЯ; НАПРИМЕР, дЖОН мАККАРТИ ПРЕДЛОЖИЛ
ВЫБИРАТЬ $K\approx{1\over2}(u+v)$, ЕСЛИ ИЗВЕСТНО, ЧТО ВСЕ КЛЮЧИ ЛЕЖАТ
В ДИАПАЗОНЕ МЕЖДУ $u$ И~$v$.

еЩЕ ОДНУ СТРАТЕГИЮ РАЗДЕЛЕНИЯ ПРЕДЛОЖИЛ м.~х.~ВАН~эМДЕН [{\sl CACM\/}, 
{\bf 13} (1970), 563--567]: ВМЕСТО ТОГО ЧТОБЫ ВЫБИРАТЬ $K$ ЗАРАНЕЕ, МЫ 
"УЗНАЕМ", КАКОВО МОЖЕТ БЫТЬ ХОРОШЕЕ ЗНАЧЕНИЕ $K$, СЛЕДЯ В ПРОЦЕССЕ 
РАЗДЕЛЕНИЯ ЗА ИЗМЕНЕНИЕМ ВЕЛИЧИН 
$K'=\max(K_l, \ldots, K_i)$ И~$K''=\min(K_j, \ldots, K_r)$. мОЖНО 
УВЕЛИЧИВАТЬ $i$ ДО ТЕХ ПОР, ПОКА НЕ ВСТРЕТИТСЯ КЛЮЧ, БОЛЬШИЙ $K'$; ЗАТЕМ 
НАЧАТЬ  УМЕНЬШАТЬ $j$, ПОКА НЕ ВСТРЕТИТСЯ КЛЮЧ, МЕНЬШИЙ $K''$, ПОСЛЕ 
ЧЕГО ПОМЕНЯТЬ ИХ МЕСТАМИ И/ИЛИ УТОЧНИТЬ ЗНАЧЕНИЯ~$K'$ И~$K''$. 
эМПИРИЧЕСКИЕ ТЕСТЫ ДЛЯ ЭТОЙ ИНТЕРВАЛЬНОЙ СОРТИРОВКИ ПОКАЗЫВАЮТ, ЧТО ОНА 
ТРЕБУЕТ ОКОЛО $1.64N\ln N=1.14N\log_2N$ СРАВНЕНИЙ. эТО ЕДИНСТВЕННЫЙ МЕТОД, 
ОБСУЖДАЕМЫЙ В ЭТОЙ КНИГЕ, ДЛЯ ПОВЕДЕНИЯ КОТОРОГО ЕЩЕ НЕ НАЙДЕНО 
АДЕКВАТНОГО ТЕОРЕТИЧЕСКОГО ОБЎЯСНЕНИЯ.

оБОБЩЕНИЕ ОБМЕННОЙ ПОРАЗРЯДНОЙ СОРТИРОВКИ НА СЛУЧАЙ СИСТЕМЫ СЧИСЛЕНИЯ С 
ОСНОВАНИЕМ, БОЛЬШИМ 2, ОБСУЖДАЕТСЯ В П.~5.2.5.
%%158

\section * аСИМПТОТИЧЕСКИЕ МЕТОДЫ. аНАЛИЗ АЛГОРИТМОВ ОБМЕННОЙ СОРТИРОВКИ 
ПРИВОДИТ К НЕКОТОРЫМ ОСОБЕННО ПОУЧИТЕЛЬНЫМ МАТЕМАТИЧЕСКИМ ЗАДАЧАМ, 
КОТОРЫЕ ПОЗВОЛЯЮТ БОЛЬШЕ УЗНАТЬ О СПОСОБАХ ОПРЕДЕЛЕНИЯ АСИМПТОТИЧЕСКОГО 
ПОВЕДЕНИЯ ФУНКЦИИ. нАПРИМЕР, ПРИ АНАЛИЗЕ МЕТОДА ПУЗЫРЬКА [ФОРМУЛА (9)] МЫ 
СТОЛКНУЛИСЬ С ФУНКЦИЕЙ
$$
W_n={1\over n!}\sum_{0\le r <s\le n} s!r^{n-s}.
\eqno(31)
$$
кАКОВО ЕЕ АСИМПТОТИЧЕСКОЕ ЗНАЧЕНИЕ?

мОЖНО ДЕЙСТВОВАТЬ ТАК ЖЕ, КАК ПРИ ИССЛЕДОВАНИИ ЧИСЛА ИНВОЛЮЦИЙ [ФОРМУЛА 
(5.1.4--41)]. пОЭТОМУ, ПРЕЖДЕ ЧЕМ ДВИГАТЬСЯ ДАЛЬШЕ, ПОЛЕЗНО ЕЩЕ РАЗ 
ПРОСМОТРЕТЬ ОБСУЖДЕНИЕ В КОНЦЕ П.~5.1.4.

иССЛЕДОВАНИЕ ФОРМУЛЫ (31) ПОКАЗЫВАЕТ, ЧТО ВКЛАД ПРИ $s=n$
БОЛЬШЕ, ЧЕМ ВКЛАД ПРИ $s=n-1$, И Т. Д.; ЭТО НАВОДИТ НА МЫСЛЬ О ЗАМЕНЕ $s$ 
НА $n-s$. мЫ СКОРО УВИДИМ, ЧТО НА САМОМ ДЕЛЕ УДОБНЕЕ ВСЕГО ПРИМЕНИТЬ 
ПОДСТАНОВКИ $t=n-s+1$, $m=n+1$, В РЕЗУЛЬТАТЕ КОТОРЫХ ФОРМУЛА (31) ПРИМЕТ ВИД
$$
{1\over m}W_{m-1}={1\over m!}\sum_{1\le t< m}(m-t)!\sum_{0\le r<m-t}r^{t-1}.
\eqno(32)
$$
дЛЯ ВНУТРЕННЕЙ СУММЫ СУЩЕСТВУЕТ ХОРОШО ИЗВЕСТНЫЙ АСИМПТОТИЧЕСКИЙ РЯД, 
ПОЛУЧЕННЫЙ ИЗ ФОРМУЛЫ СУММИРОВАНИЯ эЙЛЕРА:
$$
\eqalign{
\sum_{0\le r<N} r^{t-1} 
&={N^t\over t}-{1\over2}(N^{t-1}-\delta_{t1})+{B_2\over2!}(t-1)(N^{t-2}-\delta_{t2})+\cdots=\cr
&={1\over t}\sum_{0\le j\le k}\perm{t}{j}B_j(N^{t-j}-\delta_{tj})+O(N^{t-k})\cr
}
\eqno(33)
$$

(СМ. УПР. 1.2.11.2--4). сЛЕДОВАТЕЛЬНО, НАША ЗАДАЧА СВОДИТСЯ К ИЗУЧЕНИЮ 
СУММ ВИДА
$$
{1\over m!}\sum_{1\le t<m} (m-t)!(m-t)^t\,t^k, \quad k\ge-1.
\eqno(34)
$$
кАК И В П.~5.1.4, МОЖНО ПОКАЗАТЬ, ЧТО ПРИ ЗНАЧЕНИЯХ $t$, Б\'ОЛЬШИХ 
$m^{1/2+\varepsilon}$, ЧЛЕНЫ СУММЫ ПРЕНЕБРЕЖИМО МАЛЫ: 
$O(\exp(-n^\delta))$. зНАЧИТ, МОЖНО ПОЛОЖИТЬ $t =O(m^{1/2+\varepsilon})$ И 
ЗАМЕНИТЬ ФАКТОРИАЛЫ ПО ФОРМУЛЕ сТИРЛИНГА
$$
{(m-t)!(m-t)^t\over m!}=
\sqrt{1-{t\over m}}
\exp\left({t\over12m^2}-\left({t^2\over2m}+{t^3\over3m^2}+{t^4\over4m^3}+{t^5\over5m^4}\right)
+O(m^{-2+6\varepsilon})\right).
$$
тАКИМ ОБРАЗОМ, НАС ИНТЕРЕСУЕТ АСИМПТОТИЧЕСКОЕ ЗНАЧЕНИЕ СУММЫ
$$
r_k(m)=\sum_{1\le t<m} e^{-t^2/2m}t^k, \quad k\ge-1.
\eqno(35)
$$
%%159
(сУММИРОВАНИЕ ЗДЕСЬ ТАКЖЕ МОЖНО БЫЛО БЫ РАСПРОСТРАНИТЬ НА ВЕСЬ ДИАПАЗОН 
$1\le t<\infty$, НЕ ИЗМЕНИВ ПРИ ЭТОМ АСИМПТОТИЧЕСКОГО ЗНАЧЕНИЯ СУММЫ, 
ПОСКОЛЬКУ, КАК УКАЗАНО ВЫШЕ, ВХОДЯЩИЕ В СУММУ ЗНАЧЕНИЯ ПРИ 
$t>m^{1/2+\varepsilon}$ ПРЕНЕБРЕЖИМО МАЛЫ.)

пУСТЬ $g_k(x)=x^ke^{-x^2}$ И~$f_k(x)=g_k(x/\sqrt{2m})$. пО ФОРМУЛЕ 
СУММИРОВАНИЯ эЙЛЕРА ПРИ~$k\ge 0$
$$
\eqalign{
\sum_{0\le t<m} f_k(t)&=\int_0^m f_k(x)\,dx
+\sum_{1\le j\le p}{B_j\over j!}(f_k^{(j-1)}(m)-f_k^{(j-1)}(0))+R_p,\cr
R_p&={(-1)^{p+1}\over p!}\int_0^m B_p(\{x\})f_k^{(p)}(x)\,dx=\cr
   &\left({1\over\sqrt{2m}}\right)^p 
O\left(\int_0^\infty\abs{g_k^{(p)}(y)}\,dy\right)
=O(m^{-p/2});\cr
}
\eqno(36)
$$
СЛЕДОВАТЕЛЬНО, ПРИ ПОМОЩИ, ПО СУЩЕСТВУ, ТЕХ ЖЕ ПРИЕМОВ, ЧТО И РАНЬШЕ, 
МОЖНО ПОЛУЧИТЬ АСИМПТОТИЧЕСКИЙ РЯД ДЛЯ~$r_k(m)$, ЕСЛИ ТОЛЬКО $k\ge 0$. нО 
ПРИ $k=-1$ ЭТОТ МЕТОД НЕ ГОДИТСЯ, ТАК КАК ЗНАЧЕНИЕ $f_{-1}(0)$ НЕ 
ОПРЕДЕЛЕНО; НЕЛЬЗЯ ТАКЖЕ ПРОСТО ПРОСУММИРОВАТЬ ОТ~$1$ ДО~$m$, ТАК КАК 
ОСТАТОЧНЫЕ ЧЛЕНЫ НЕ ДАЮТ УБЫВАЮЩИХ СТЕПЕНЕЙ~$m$, ЕСЛИ НИЖНИЙ ПРЕДЕЛ 
РАВЕН~$1$. (иМЕННО В ЭТОМ СУТЬ ДЕЛА, И, ПРЕЖДЕ ЧЕМ ДВИГАТЬСЯ ДАЛЬШЕ, 
ЧИТАТЕЛЬ ДОЛЖЕН УБЕДИТЬСЯ В ТОМ, ЧТО ОН ХОРОШО ПОНЯЛ ЗАДАЧУ.)

чТОБЫ РАЗРЕШИТЬ ЭТУ ДИЛЕММУ, МОЖНО ПОЛОЖИТЬ ПО ОПРЕДЕЛЕНИЮ 
$g_{-1}(x)=(e^{-x^2}-1)/x$, $f_{-1}(x)=g_{-1}(x/\sqrt{2m})$; ТОГДА 
$f_{-1}(0)=0$ И $r_{-1}(m)$ НЕТРУДНО ПОЛУЧИТЬ 
ИЗ~$\sum_{0\le t< m} f_{-1}(t)$. уРАВНЕНИЕ (36) СПРАВЕДЛИВО ТЕПЕРЬ И 
ПРИ~$k=-1$, А ОСТАВШИЙСЯ ИНТЕГРАЛ НАМ "ХОРОШО ЗНАКОМ" (СМ. УПР. 43):
$$
\eqalign{
{2\over\sqrt{2m}}\int_0^m f_{-1}(x)\,dx&=
   2\int_0^m{e^{-x^2/2m}-1\over x}\,dx=\int_0^{m/2}{e^{-y}-1\over y}\,dy=\cr
&=\int_0^1{e^{-y}-1\over y}\,dy+\int_1^{m/2}{e^{-y}\over y}\,dy-\ln(m/2)=\cr
&=-\gamma-\ln(m/2)+O(e^{-m/2}).\cr
}
$$

тЕПЕРЬ У НАС ДОСТАТОЧНО ФОРМУЛ И ФАКТОВ ДЛЯ ТОГО, ЧТОБЫ ВЫВЕСТИ НАКОНЕЦ 
ОТВЕТ, КОТОРЫЙ РАВЕН, КАК ПОКАЗАНО В ОТВЕТЕ К УПР~ 44,
$$
W_n={1\over2}m\ln m+{1\over2}(\gamma+\ln2)m-{2\over3}\sqrt{2\pi m}
+{31\over36}+O(n^{-1/2}), \quad m=n+1.
\eqno(37)
$$
эТИМ ЗАВЕРШАЕТСЯ АНАЛИЗ МЕТОДА ПУЗЫРЬКА.

%% 160

чТОБЫ ПРОАНАЛИЗИРОВАТЬ ОБМЕННУЮ ПОРАЗРЯДНУЮ СОРТИРОВКУ, НЕОБХОДИМО ЗНАТЬ 
АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ ПРИ $n\to\infty$ КОНЕЧНОЙ СУММЫ
$$
U_n=\sum_{k\ge2}\perm{n}{k}(-1)^k{1\over 2^{k-1}-1}.
\eqno(38)
$$
эТОТ ВОПРОС ОКАЗЫВАЕТСЯ ГОРАЗДО СЛОЖНЕЕ ДРУГИХ ЗАДАЧ ОБ АСИМПТОТИЧЕСКОМ 
ПОВЕДЕНИИ, С КОТОРЫМИ МЫ СТАЛКИВАЛИСЬ ДО СИХ ПОР;
ЭЛЕМЕНТАРНЫЕ МЕТОДЫ РАЗЛОЖЕНИЯ В СТЕПЕННЫЕ РЯДЫ, ФОРМУЛА СУММИРОВАНИЯ 
эЙЛЕРА И Т. Д. ЗДЕСЬ БЕССИЛЬНЫ. сЛЕДУЮЩИЙ ВЫВОД БЫЛ ПРЕДЛОЖЕН н.~г.~ДЕ~ бРЕЙНОМ.

чТОБЫ ИЗБАВИТЬСЯ В ФОРМУЛЕ (38) ОТ ПОДАВЛЯЮЩЕГО ВЛИЯНИЯ
БОЛЬШИХ МНОЖИТЕЛЕЙ $\perm{n}{k} (-1)^k$, МЫ НАЧНЕМ С ТОГО, ЧТО ПЕРЕПИШЕМ 
СУММУ В ВИДЕ БЕСКОНЕЧНОГО РЯДА:
$$
U_n=\sum_{k\ge2}\perm{n}{k}(-1)^k\sum_{j\ge1}\left({1\over2^k-1}\right)^j=
\sum_{j\ge1}(2^j(1-2^{-j})^n-2^j+n).
\eqno(39)
$$

еСЛИ ПОЛОЖИТЬ $x=n/2^j$, ТО ЧЛЕН РЯДА ЗАПИШЕТСЯ В ВИДЕ
$$
2^j(1-2^{-j})^n-2^j+n=
{n\over x}\left(\left(1-{x\over n}\right)^n-1+x\right).
$$
пРИ $x\le n^\varepsilon$ ИМЕЕМ
$$
\left(1-{x\over n}\right)^n=\exp\left(n\ln\left(1-{x\over n}\right)\right)
=\exp(-x+x^2O(n^{-1})),
\eqno(40)
$$
А ЭТО НАВОДИТ НА МЫСЛЬ О ТОМ, ЧТОБЫ ПРИБЛИЗИТЬ (39) РЯДОМ
$$
T_n=\sum_{j\ge1}(2^je^{-n/2^j}-2^j+n).
\eqno(41)
$$
чТОБЫ ОПРАВДАТЬ ЭТО ПРИБЛИЖЕНИЕ, РАССМОТРИМ РАЗНОСТЬ 
$U_n-T_n=X_n+Y_n$, ГДЕ
$$
\eqalignno{
X_n&=
\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j<n^{1-\varepsilon}}
    (2^j(1-2^{-j})^n-2^je^{-n/2^j})=
    &\rem{[Т.Е. СЛАГАЕМЫЕ ПРИ $x>n^\varepsilon$]}\cr
&=\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j<n^{1-\varepsilon}} 
    O(ne^{-n/2^j})=
    &\rem{[ТАК КАК $0<1-2^{-j}<e^{-2^{-j}}$]}\cr
&=O(n\log n e^{-n^\varepsilon})
    &\rem{[ТАК КАК ИМЕЕТСЯ $O(\log n)$СЛАГАЕМЫХ];}\cr
Y_n&=
\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j\ge n^{1-\varepsilon}}
    (2^j(1-2^{-j})^n-2^je^{-n/2^j})=
    &\rem{[СЛАГАЕМЫЕ ПРИ $x\le n^{-\varepsilon}$]}\cr
&=\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j\ge n^{1-\varepsilon}}
    \left(e^{-n/2^j}\left({n\over2^j}\right)O(1)\right)
    &\rem{[ПО ФОРМУЛЕ (40)]}\cr
}
$$
%% 161

\bye