\input style
{ \catcode`\[=\active\def[{\hbox to 0pt{\hss$\lbrack$}}
 \catcode`\]=\active\def]{\hbox to 0pt{$\rbrack$\hss}}
\htable{тАБЛИЦА 2}{"бЫСТРАЯ СОРТИРОВКА"}{
$\phantom{[}#\phantom{]}$\bskip&&$\phantom{[}#\phantom{]}$\bskip\cr
    &     &     &    &     &     &    &    &    &     &     &     &    &     &     &     & (l, r) & \hbox{сТЕК}\cr
\noalign{\hrule}
[503& 087 & 512 & 061& 908 & 170 & 897& 275& 653& 426 & 154 & 509 & 612& 677 & 765 & 703]& (1,16) & - \cr
[154& 087 & 426 & 061& 275 & 170]& 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (1,6)  & (8,16)\cr
[061& 087]& 154 &[426& 275 & 170]& 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (1,2)  & (4,6)(8,16)\cr
 061& 087 & 154 &[426& 275 & 170]& 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (4,6)  & (8,16)\cr
 061& 087 & 154 &[170& 275]& 426 & 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (4,5)  & (8, 16)\cr
 061& 087 & 154 & 170& 275 & 426 & 503&[897& 653& 908 & 512 & 509 & 612& 677 & 765 & 703]& (8,16) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503&[703& 653& 765 & 512 & 509 & 612& 677]& 897 & 908 & (8,14) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503&[677& 653& 612 & 512 & 509]& 703& 765 & 897 & 908 & (8,12) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503&[509& 653& 612 & 512]& 677 & 703& 765 & 897 & 908 & (8,11) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503& 509&[653& 612 & 512]& 677 & 703& 765 & 897 & 908 & (9,11) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503& 509&[512& 612]& 653 & 677 & 703& 765 & 897 & 908 & (9,10) & - \cr
 061& 087 & 154 & 170& 275 & 426 & 503& 509& 512& 612 & 653 & 677 & 703& 765 & 897 & 908 &    -   & - \cr
\noalign{\hrule}
}}
тОЛЬКО ЧТО ОПИСАННУЮ ПРОЦЕДУРУ СОРТИРОВКИ МОЖНО НАЗВАТЬ ОБМЕННОЙ  
СОРТИРОВКОЙ  \emph{С  РАЗДЕЛЕНИЕМ;} ОНА  ПРИНАДЛЕЖИТ ч.~э.~р.~хОАРУ, 
ИНТЕРЕСНЕЙШАЯ СТАТЬЯ КОТОРОГО 
[{\sl Comp. J.,\/} {\bf 5} (1962), 10--15]---ОДНО ИЗ НАИБОЛЕЕ ИСЧЕРПЫВАЮЩИХ 
ИЗ КОГДА-ЛИБО ОПУБЛИКОВАННЫХ СООБЩЕНИЙ ОБ ЭТОМ МЕТОДЕ. хОАР ОКРЕСТИЛ 
СВОЙ МЕТОД "quicksort" ("БЫСТРАЯ СОРТИРОВКА"), И ЭТО НАЗВАНИЕ 
ВПОЛНЕ СООТВЕТСТВУЕТ ДЕЙСТВИТЕЛЬНОСТИ, ТАК КАК, НАПРИМЕР, ВЕСЬ ПРОЦЕСС 
СОРТИРОВКИ, ПОКАЗАННЫЙ В ТАБЛ.~2, ТРЕБУЕТ ВСЕГО 48~СРАВНЕНИЙ (МЕНЬШЕ 
ЛЮБОГО ДРУГОГО ВСТРЕЧАВШЕГОСЯ УЖЕ МЕТОДА, ЗА ИСКЛЮЧЕНИЕМ БИНАРНЫХ ВСТАВОК, 
ТРЕБУЮЩИХ 47~СРАВНЕНИЙ).
\picture{рИС ~19.  оБМЕННАЯ СОРТИРОВКА С РАЗДЕЛЕНИЕМ ("БЫСТРАЯ СОРТИРОВКА").}
вО ВСЕХ СРАВНЕНИЯХ НА ДАННОЙ СТАДИИ УЧАСТВУЕТ ОДИН И ГОТ ЖЕ КЛЮЧ, ТАК ЧТО 
ЕГО МОЖНО ХРАНИТЬ В РЕГИСТРЕ. кРОМЕ ТОГО, КОЛИЧЕСТВО ПЕРЕМЕЩЕНИЙ ДАННЫХ 
ВЕСЬМА УМЕРЕННО: ПРИ ВЫЧИСЛЕНИЯХ ТАБЛ.~2 ПРОИЗВЕДЕНО ВСЕГО $17$~ОБМЕНОВ, 
ПРИЧЕМ БОЛЬШИНСТВО ИЗ НИХ---ПРОСТО "ПОЛУОБМЕНЫ" (ПРОСТЫЕ ПЕРЕСЫЛКИ), ТАК КАК ОДИН
%% 143
ИЗ КЛЮЧЕЙ ВСЕ ВРЕМЯ ОСТАЕТСЯ В РЕГИСТРЕ, И ЕГО НЕ НУЖНО ЗАПИСЫВАТЬ ДО 
САМОГО КОНЦА СТАДИИ.

вСПОМОГАТЕЛЬНЫЕ ОПЕРАЦИИ (ТРЕБУЕМЫЕ ДЛЯ УПРАВЛЕНИЯ СТЕКОМ И 
ПЕРЕМЕННЫМИ~$i$, $j$) НЕ СЛОЖНЫ, НО ИЗ-ЗА НИХ ПРОЦЕДУРА БЫСТРОЙ СОРТИРОВКИ 
ПОСРЕДСТВОМ РАЗДЕЛЕНИЙ ПРИГОДНА В ОСНОВНОМ ДЛЯ БОЛЬШИХ ЗНАЧЕНИЙ~$N$; 
ПОЭТОМУ КОРОТКИЕ ПОДФАЙЛЫ ЖЕЛАТЕЛЬНО СОРТИРОВАТЬ ОСОБОМ ОБРАЗОМ, КАК ЭТО 
ДЕЛАЕТСЯ В СЛЕДУЮЩЕМ АЛГОРИТМЕ.

\alg Q.(оБМЕННАЯ СОРТИРОВКА С РАЗДЕЛЕНИЕМ.) зАПИСИ~$R_1$,~\dots, $R_N$ 
ПЕРЕРАЗМЕЩАЮТСЯ НА ТОМ ЖЕ МЕСТЕ; ПОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ ИХ КЛЮЧИ 
БУДУТ УПОРЯДОЧЕНЫ: $K_1\le\ldots\le K_N$. нУЖЕН ВСПОМОГАТЕЛЬНЫЙ СТЕК ДЛЯ 
ХРАНЕНИЯ НЕ БОЛЕЕ ЧЕМ $\log_2 N$~ЭЛЕМЕНТОВ. эТОТ АЛГОРИТМ СООТВЕТСТВУЕТ 
ПРОЦЕДУРЕ "БЫСТРОЙ СОРТИРОВКИ" ПОСРЕДСТВОМ РАЗДЕЛЕНИЙ, ПРИВЕДЕННОЙ ВЫШЕ, С 
НЕБОЛЬШИМИ ИЗМЕНЕНИЯМИ В ЦЕЛЯХ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ:
{\medskip\narrower
\item{a)}~пРЕДПОЛАГАЕТСЯ НАЛИЧИЕ ИСКУССТВЕННЫХ КЛЮЧЕЙ~$K_0=-\infty$ 
И~$K_{N+1}=+\infty$, ТАКИХ, ЧТО
$$
K_0\le K_i \le K_{N+1} \rem{ПРИ~$1\le i \le N$.}
\eqno (13)
$$
(рАВЕНСТВО ДОПУСКАЕТСЯ.)

\item{b)}~пОДФАЙЛЫ, СОСТОЯЩИЕ ИЗ~$M$ И МЕНЕЕ ЭЛЕМЕНТОВ, СОРТИРУЮТСЯ 
ПРОСТЫМИ ВСТАВКАМИ, ГДЕ~$M\ge 1$---ПАРАМЕТР, КОТОРЫЙ ВЫБИРАЕТСЯ, КАК ОПИСАНО НИЖЕ.

\item{c)}~нА НЕКОТОРЫХ СТАДИЯХ ДЕЛАЕТСЯ ОДНО ИЛИ ДВА ДОПОЛНИТЕЛЬНЫХ 
СРАВНЕНИЯ (ДОПУСКАЕТСЯ ПЕРЕКРЫТИЕ УКАЗАТЕЛЕЙ~$i$, $j$), ЧТОБЫ ОСНОВНЫЕ 
ЦИКЛЫ СРАВНЕНИЯ ВЫПОЛНЯЛИСЬ НАСТОЛЬКО БЫСТРО, НАСКОЛЬКО ЭТО ВОЗМОЖНО.

\item{d)}~зАПИСИ С ОДИНАКОВЫМИ КЛЮЧАМИ МЕНЯЮТСЯ МЕСТАМИ, ХОТЯ ЭТО НЕ 
ЯВЛЯЕТСЯ СТРОГО НЕОБХОДИМЫМ. (эТА ИДЕЯ, ПРИНАДЛЕЖАЩАЯ р.~к.~сИНГЛТОНУ, 
СПОСОБСТВУЕТ РАЗДЕЛЕНИЮ ПОДФАЙЛОВ ПОЧТИ ПОПОЛАМ, ЕСЛИ ИМЕЮТСЯ РАВНЫЕ 
КЛЮЧИ; СМ.~УПР.~18.)
\medskip}

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

\st[нАЧАТЬ НОВУЮ СТАДИЮ.] (нАМ ХОТЕЛОСЬ БЫ ОТСОРТИРОВАТЬ ФАЙЛ~$R_l$,~\dots,
$R_r$; ИЗ САМОГО СУЩЕСТВА АЛГОРИТМА ВЫТЕКАЕТ, ЧТО~$r\ge l-1$, 
$K_{l-1}\le K_i \le K_{r+1}$ ПРИ~$l\le i \le r$.) еСЛИ~$r-l<M$, ТО ПЕРЕЙТИ К 
ШАГУ~\stp{8}. в ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ~$i\asg l$, $j\asg r$, $K\asg K_l$, 
$R\asg R_l$. (оБСУЖДЕНИЕ НАИЛУЧШЕГО ВЫБОРА~$R$ И~$K$ ПРИВЕДЕНО НИЖЕ.)

\st[сРАВНИТЬ~$K:K_j$.] еСЛИ~$K<K_j$, ТО УМЕНЬШИТЬ~$j$ НА~$1$ И ПОВТОРИТЬ 
ЭТОТ ШАГ.

\st[пЕРЕСЛАТЬ~$R$ НА МЕСТО~$R_i$.] (к ЭТОМУ МОМЕНТУ $K_i$---КЛЮЧ~$\ge K$, 
НАХОДЯЩИЙСЯ НЕ НА СВОЕМ МЕСТЕ, И~$K\ge K_j$.) еСЛИ~$j\le i$, ТО 
УСТАНОВИТЬ~$R_i\asg R$ И ПЕРЕЙТИ К ШАГУ~Q7. в ПРОТИВНОМ СЛУЧАЕ 
УСТАНОВИТЬ~$R_i\asg R_j$ И УВЕЛИЧИТЬ~$i$ НА~1.
%%144
\st[сРАВНИТЬ~$K_i:K$.] еСЛИ~$K_i<K$, ТО УВЕЛИЧИТЬ~$i$ НА~$1$ И ПОВТОРИТЬ 
ЭТОТ ШАГ.

\st[пЕРЕСЛАТЬ~$R$ НА МЕСТО~$R_j$.] (к ЭТОМУ МОМЕНТУ $K_j$---КЛЮЧ~$\le K$, 
НАХОДЯЩИЙСЯ НЕ НА СВОЕМ МЕСТЕ, И~$K\le K_i$.) еСЛИ~$j\le i$, ТО 
УСТАНОВИТЬ~$R_j\asg R$ И~$i\asg j$. в ПРОТИВНОМ СЛУЧАЕ 
УСТАНОВИТЬ~$R_j\asg R_i$,  УМЕНЬШИТЬ~$j$ НА~$1$ И ПЕРЕЙТИ К ШАГУ~\stp{3}.

\st[пОМЕСТИТЬ В СТЕК.] (тЕПЕРЬ ПОДФАЙЛ~$R_l\ldots{}R_i\ldots{}R_r$ 
РАЗДЕЛЕН ТАК, ЧТО~$K_k\le K_i$ ПРИ~$l\le k \le i$ И~$K_i\le K_k$ 
ПРИ~$i\le k \le r$ .) еСЛИ~$r-i\ge i-l$, ТО ПОМЕСТИТЬ В СТЕК~$(i+1, r)$ И 
УСТАНОВИТЬ~$r\asg i-1$. в ПРОТИВНОМ СЛУЧАЕ ПОМЕСТИТЬ В СТЕК~$(l, i-1)$ 
И УСТАНОВИТЬ~$l\asg i+1$. (кАЖДЫЙ ЭЛЕМЕНТ СТЕКА~$(a, b)$---ЭТО ЗАЯВКА НА 
СОРТИРОВКУ ПОДФАЙЛА~$R_a\ldots{}R_b$ В ОДНОЙ ИЗ ПОСЛЕДУЮЩИХ СТАДИЙ.) 
вЕРНУТЬСЯ К ШАГУ~\stp{2}.

\st[сОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ.] дЛЯ~$j=l+1$, $l+2$,~\dots{} ДО~$j>r$ 
ВЫПОЛНЯТЬ СЛЕДУЮЩИЕ ОПЕРАЦИИ: УСТАНОВИТЬ~$K\asg K_j$, $R\asg R_j$, $i\asg j-1$; 
ЗАТЕМ УСТАНОВИТЬ~$R_{i+1}\asg R_i$, $i\asg i-1$ НУЛЬ ИЛИ БОЛЕЕ РАЗ 
ДО ТЕХ ПОР, ПОКА НЕ ВЫПОЛНИТСЯ УСЛОВИЕ~$K_i\le K$; ЗАТЕМ 
УСТАНОВИТЬ~$R_{i+1}\asg R$. (эТО, ПО СУЩЕСТВУ, АЛГОРИТМ~5.2.1S, 
ПРИМЕНЕННЫЙ К ПОДФАЙЛУ ИЗ~$M$ ИЛИ МЕНЕЕ ЭЛЕМЕНТОВ.)

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

сООТВЕТСТВУЮЩАЯ \MIX-ПРОГРАММА ДОВОЛЬНО ВЕЛИКА, НО НЕ СЛОЖНА; НА САМОМ 
ДЕЛЕ БОЛЬШАЯ ЧАСТЬ КОМАНД ОТНОСИТСЯ К Шary~Q7, В КОТОРОМ ПРОВОДЯТСЯ ВЕСЬМА 
ПРОСТЫЕ МАНИПУЛЯЦИИ С ПЕРЕМЕННЫМИ.

\prog Q.(оБМЕННАЯ СОРТИРОВКА С РАЗДЕЛЕНИЕМ.) зАПИСИ, КОТОРЫЕ ПРЕДСТОИТ 
ОТСОРТИРОВАТЬ, НАХОДЯТСЯ В ЯЧЕЙКАХ $|INPUT|+1$,~\dots, $|INPUT|+N$; 
ПРЕДПОЛАГАЕТСЯ, ЧТО В ЯЧЕЙКАХ~|INPUT| И~$|INPUT|+N+1$ СОДЕРЖАТСЯ ЗНАЧЕНИЯ, 
СООТВЕТСТВЕННО МИНИМАЛЬНО, И МАКСИМАЛЬНО ДОПУСТИМЫЕ В МАШИНЕ~\MIX. 
сТЕК РАСПОЛАГАЕТСЯ В ЯЧЕЙКАХ $|STACK|+1$, $|STACK|+2$,~\dots; ТОЧНОЕ ЧИСЛО 
ЯЧЕЕК, КОТОРОЕ НЕОБХОДИМО ОТВЕСТИ ПОД СТЕК, ОБСУЖДАЕТСЯ В УПР.~20. 
зНАЧЕНИЯ РЕГИСТРОВ: $|rI1|\equiv l$, $|rI2|\equiv r$, $|rI3|\equiv i$, 
$|rI4|\equiv j$, $|rI6|\equiv \hbox{РАЗМЕР СТЕКА}$, $|rA|\equiv K \equiv R$.
\code
A    & EQU  & 2:3       &      & пЕРВАЯ КОМПОНЕНТА ЭЛЕМЕНТА СТЕКА.
в    & EQU  & 4:5       &      & вТОРАЯ КОМПОНЕНТА ЭЛЕМЕНТА СТЕКА.
START& ENT1 & 1         & 1    & Q1. нАЧАЛЬНАЯ УСТАНОВКА. $l\asg1$.
     & ENT2 & N         & 1    & $r\asg N$.
     & ENT6 & 0         & 1    & оПУСТОШИТЬ СТЕК.
2H   & ENTX & 0,2       & 2A+1 & Q2. нАЧАТЬ НОВУЮ СТАДИЮ.
     & DECX & M,1       & 2A+1 & $|rX|\asg r-l-M$.
%%145
     & JXN  & 8F        & 2A+1 & к ШАГУ~Q8, ЕСЛИ РАЗМЕР ПОДФАЙЛА~$\le M$.
     & ENT3 & 0,1       & A    & $i\asg l$.
     & ENT4 & 0,2       & A    & $j\asg r$.
     & LDA  & INPUT,3   & A    & $K\asg K_i$.
     & JMP  & 3F        & A    & к ШАГУ~Q3.
0H   & LDX  & INPUT,3   & B
     & STX  & INPUT,4   & B    & $R_j\asg R_i$.
     & DEC4 & 1         & C'-A & $j\asg j-1$.
3H   & CMPA & INPUT,4   & C'   & Q3.~сРАВНИТЬ~$K:K_j$.
     & JL   & *-2       & C'   & еСЛИ~$<$, ТО УМЕНЬШИТЬ~$j$ И ПОВТОРИТЬ.
4H   & ENTX & 0,3       & B+A  & Q4.~пЕРЕСЛАТЬ~$R$ НА МЕСТО~$R_i$.
     & DECX & 0,4       & B+A
     & JXNN & 7F        & B+A  & к ШАГУ~Q7, ЕСЛИ~$i\ge j$.
     & LDX  & INPUT,4   & B+X
     & STX  & INPUT,3   & B+X  & $R_i\asg R_j$.
     & INC3 & 1         & C''  & $i\asg i+1$.
5H   & смра & INPUT,3   & C''  & Q5.~сРАВНИТЬ~$K_i:K$.
     & JG   & *-2       & C''  & еСЛИ~$<$, ТО УВЕЛИЧИТЬ~$i$ И ПОВТОРИТЬ.
6H   & ENTX & 0,3       & B+X  & Q6.~пЕРЕСЛАТЬ~$R$ НА МЕСТО~$R_i$.
     & DECX & 0,4       & B+X 
     & JXN  & 0B        & B+X  & к ШАГУ~Q3, ЕСЛИ~$i<j$.
     & ENT3 & 0,4       & X    & $i\asg j$.
7H   & STA  & INPUT,3   & A    & Q7. пОМЕСТИТЬ В СТЕК. $R_i\asg R$.
     & ENTA & 0,2       & A
     & DECA & 0,3       & A
     & DECA & 0,3       & A
     & INCA & 0,1       & A
     & INC6 & 1         & A    & $|rI6|\asg |rI6|+1$.
     & JANN & 1F        & A    & пЕРЕХОД, ЕСЛИ~$r-i\ge i-l$.
     & ST1  & STACK,6(A)& A'
     & DEC3 & 1         & A'
     & ST3  & STACK,6(B)& A'   & $(l, i-1)\Rasg \hbox{СТЕК}$.
     & ENT1 & 2,3       & A'   & $l\asg i+1$.
     & JMP  & 2B        & A'   & к ШАГУ~Q2.
1H   & INC3 & 1         & A-A'
     & ST3  & STACK,6(A)& A-A'
     & ST2  & STACK,6(B)& A-A' & $(i+1, r)\Rasg\hbox{СТЕК}$.
     & ENT2 & -2,3      & A-A' & $r\asg i-1$.
     & JMP  & 2B        & A-A' & к ШАГУ~Q2.
8H   & DEC2 & 0,1       & A+1  & Q8. сОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ.
     & J2NP & 9F        & A+1  & к ШАГУ~Q9, ЕСЛИ~$r\le l$.
     & ENT4 & 1,1       & A+1-L& $j\asg l+1$.
1H   & LDA  & INPUT,4   & D    & $R\asg R_j$.
     & ENT3 & -1,4      & D    & $i\asg j-1$.
     & JMP  & *+4       & D    & пЕРЕХОД И ЦИКЛ.
     & LDX  & INPUT,3   & E
     & STX  & INPUT+1,3 & E    & $R_{i+1}\asg R_i$.
     & DEC3 & 1         & E    & $i\asg i-1$.
     & смра & INPUT,3   & D+E
     & JL   & *-4       & D+E  & пЕРЕХОД, ЕСЛИ~$K<K_i$.
     & STA  & INPUT+1,3 & D    & $R_{i+1}\asg R$.
%% 146
     & INC4 & 1         & D    & $j\asg j+1$.
     & DEC2 & 1         & D
     & J2P  & 1B        & D    & пОВТОРИТЬ $r-l$~РАЗ.
9H   & LD1  & STACK,6(A)& A+1  & Q9. вЗЯТЬ ИЗ СТЕКА.
     & LD2  & STACK,6(B)& A+1  & $(l, r)\Asg\hbox{СТЕК}$.
     & DEC6 & 1         & A+1  & $|rI6|\asg|rI6|-1$.
     & J6NN & 2B        & A+1  & к ШАГУ~Q2, ЕСЛИ СТЕК НЕ БЫЛ ПУСТ.
\endcode
\progend
\section аНАЛИЗ "БЫСТРОЙ СОРТИРОВКИ". иНФОРМАЦИЮ О ВРЕМЕНИ ВЫПОЛНЕНИЯ, 
ПРИВЕДЕННУЮ ВМЕСТЕ С ПРОГРАММОЙ~Q, НЕТРУДНО ВЫВЕСТИ ИЗ ЗАКОНА кИРХГОФА, 
ИЛИ ЗАКОНА СОХРАНЕНИЯ (СМ.~П.~1.3.3), И ИЗ ТОГО ФАКТА, ЧТО ВСЕ ПОМЕЩЕННОЕ 
В СТЕК В КОНЦЕ КОНЦОВ ОТТУДА ИЗВЛЕКАЕТСЯ. оБЩЕЕ ВРЕМЯ РАБОТЫ ЗАВИСИТ ОТ 
СЛЕДУЮЩИХ ВЕЛИЧИН:
$$
\eqalign{
  A&=\hbox{ЧИСЛО СТАДИЙ, НА КОТОРЫХ ДАННЫЙ ПОДФАЙЛ СОДЕРЖИТ БОЛЕЕ $M$~ЭЛЕМЕНТОВ;}\cr
  B&=\hbox{ЧИСЛО ПРИСВАИВАНИЙ~$R_j\asg R_i$ В ШАГЕ~Q6;}\cr
 C'&=\hbox{ЧИСЛО ВЫПОЛНЕНИЙ ШАГА~Q3;}\cr
C''&=\hbox{ЧИСЛО ВЫПОЛНЕНИЙ ШАГА~Q5;}\cr
  D&=\hbox{ЧИСЛО ПРИСВАИВАНИЙ~$R\asg R_j$ В ШАГЕ~Q8;}\cr
  E&=\hbox{ЧИСЛО ПРИСВАИВАНИЙ~$R_{i+1}\asg R_i$ В ШАГЕ~Q8;}\cr
  L&=\hbox{ЧИСЛО СЛУЧАЕВ, КОГДА В ШАГЕ~Q8 $r\le l$;}\cr
  X&=\hbox{ЧИСЛО ОПЕРАЦИЙ~$i\asg j$ В ШАГЕ Q6.}\cr
}
\eqno(14)
$$
мЫ НЕ БУДЕМ АНАЛИЗИРОВАТЬ ВЕЛИЧИНЫ~$C'$ И~$C''$ НЕЗАВИСИМО, А РАССМОТРИМ ЛИШЬ
$$
C=C'+C''=\hbox{ОБЩЕЕ ЧИСЛО СРАВНЕНИЙ},
\eqno(15)
$$
ТАК КАК ВРЕМЯ РАБОТЫ ДЛЯ~$C'$ И~$C''$ ОДИНАКОВО. иЗУЧИВ СЕМЬ ВЕЛИЧИН: 
$A$, $B$, $C$, $D$, $E$, $L$ И~$X$, МЫ СМОЖЕМ РАЗУМНО ВЫБРАТЬ ПАРАМЕТР~$M$,
КОТОРЫМ ОПРЕДЕЛЯЕТСЯ "ПОРОГ" МЕЖДУ СОРТИРОВКОЙ ПРОСТЫМИ ВСТАВКАМИ И 
РАЗДЕЛЕНИЕМ. (еСЛИ ЧИТАТЕЛЬ НЕ МАТЕМАТИК, ОН МОЖЕТ ПРОПУСТИТЬ ВСЕ ВПЛОТЬ 
ДО ФОРМУЛ~(25).)

кАК И ПРИ АНАЛИЗЕ БОЛЬШИНСТВА ДРУГИХ АЛГОРИТМОВ В ЭТОЙ ГЛАВЕ, МЫ БУДЕМ 
ПРЕДПОЛАГАТЬ, ЧТО СОРТИРУЕМЫЕ КЛЮЧИ РАЗЛИЧНЫ;. В УПР.~18 ПОКАЗАНО, ЧТО 
НАЛИЧИЕ РАВНЫХ КЛЮЧЕЙ НЕ СНИЖАЕТ СУЩЕСТВЕННО ЭФФЕКТИВНОСТИ АЛГОРИТМА~Q; 
В ДЕЙСТВИТЕЛЬНОСТИ ПРИСУТСТВИЕ РАВНЫХ КЛЮЧЕЙ, ПО-ВИДИМОМУ, ДАЖЕ 
СПОСОБСТВУЕТ ЕЕ УВЕЛИЧЕНИЮ. тАК КАК МЕТОД ЗАВИСИТ ТОЛЬКО ОТ 
ОТНОСИТЕЛЬНОГО РАСПОЛОЖЕНИЯ КЛЮЧЕЙ, ТО МОЖНО ПРЕДПОЛАГАТЬ ТАКЖЕ, ЧТО 
ЭТО ПРОСТО ЧИСЛА~$\set{1, 2,~\ldots, N}$, РАСПОЛОЖЕННЫЕ В НЕКОТОРОМ ПОРЯДКЕ.

кОГДА МЫ ВПЕРВЫЕ ДОСТИГАЕМ ШАГА~Q2, СОРТИРОВКА СВОДИТСЯ К ПРОСТЫМ ВСТАВКАМ,
ЕСЛИ~$N\le M$, А ЭТО МЫ УЖЕ ИЗУЧИЛИ; ПОЭТОМУ ПРЕДПОЛОЖИМ, ЧТО~$N>M$. 
нЕОБХОДИМО ЛИШЬ РАЗОБРАТЬСЯ В ВЫЧИСЛЕНИЯХ, КОТОРЫЕ В ПЕРВЫЙ РАЗ ПРИВОДЯТ К ШАГУ~Q7;
%% 147
НЕТРУДНО ВИДЕТЬ, ЧТО ПРИ РАЗДЕЛЕНИИ ЗАПИСИ В ОБОИХ 
ПОДФАЙЛАХ $R_1\ldots{}R_{i-1}$ И~$R_{i+1}\ldots{}R_N$ БУДУТ РАСПОЛОЖЕНЫ В 
СЛУЧАЙНОМ ПОРЯДКЕ, ЕСЛИ ТОЛЬКО ЗАПИСИ ИСХОДНОГО ФАЙЛА БЫЛИ РАСПОЛОЖЕНЫ В 
СЛУЧАЙНОМ ПОРЯДКЕ. зНАЧИТ, ВКЛАД ПОСЛЕДУЮЩИХ ВЫЧИСЛЕНИЙ МОЖНО ОПРЕДЕЛИТЬ, 
ПРИМЕНИВ ИНДУКЦИЮ ПО~$N$.

пУСТЬ~$s$---ЗНАЧЕНИЕ ПЕРВОГО КЛЮЧА~$K_1$, И ПРЕДПОЛОЖИМ, ЧТО РОВНО~$t$ ИЗ 
КЛЮЧЕЙ~$K_1$,~\dots, $K_s$ ПРЕВОСХОДЯТ~$s$. пУСТЬ
$$
h=\cases{
1, & ЕСЛИ~$K_s<s$; \cr
0, & ЕСЛИ~$K_s\ge s$.
}
\eqno(16)
$$
иНАЧЕ ГОВОРЯ, $h=1$, ЕСЛИ КЛЮЧ, КОТОРЫЙ ВНАЧАЛЕ ЗАНИМАЛ ПОЗИЦИЮ~$s$ 
(КУДА ПОПАДЕТ КЛЮЧ~$K_1$), БУДЕТ ПЕРЕМЕЩЕН ВЛЕВО. нАПОМНИМ, ЧТО 
СОРТИРУЕМЫЕ КЛЮЧИ ЯВЛЯЮТСЯ ЦЕЛЫМИ ЧИСЛАМИ ИЗ МНОЖЕСТВА~$\set{1, 2,~\ldots, N}$.

еСЛИ~$s=1$, ТО НЕТРУДНО ВИДЕТЬ, ЧТО ПРОИЗОЙДЕТ ВО ВРЕМЯ ПЕРВОЙ СТАДИИ 
РАЗДЕЛЕНИЯ. шАГ~Q3 ВЫПОЛНИТСЯ $N$~РАЗ, ПОСЛЕ ЧЕГО ШАГ~Q4 ПРИВЕДЕТ НАС К~Q7.
тАКИМ ОБРАЗОМ, ПЕРВАЯ СТАДИЯ В ЭТОМ СЛУЧАЕ ДАСТ ТАКИЕ ВКЛАДЫ: $A=1$, 
$B=0$, $C=N$, $X=0$. аНАЛОГИЧНЫЕ, НО НЕСКОЛЬКО БОЛЕЕ СЛОЖНЫЕ РАССУЖДЕНИЯ 
ДЛЯ СЛУЧАЯ~$s>1$ (СМ.~УПР.~21) ПОКАЗЫВАЮТ, ЧТО ВКЛАДАМИ ПЕРВОЙ СТАДИИ В 
СУММАРНОЕ ВРЕМЯ ВЫПОЛНЕНИЯ В ОБЩЕМ СЛУЧАЕ БУДУТ
$$
A=1,\quad B=t, \quad C=N+1-\delta_{s1},\quad X=h \rem{ПРИ~$1<s\le N$.}
\eqno(17)
$$
к ЭТОМУ НЕОБХОДИМО ДОБАВИТЬ ВКЛАДЫ ДОСЛЕДУЮЩИХ СТАДИЙ, ВО ВРЕМЯ КОТОРЫХ 
УПОРЯДОЧИВАЮТСЯ ПОДФАЙЛЫ СООТВЕТСТВЕННО ИЗ~$s-1$ И~$N-S$~ЭЛЕМЕНТОВ.

еСЛИ ПРЕДПОЛОЖИТЬ, ЧТО В ИСХОДНОМ ФАЙЛЕ ЗАПИСИ РАСПОЛАГАЛИСЬ В СЛУЧАЙНОМ 
ПОРЯДКЕ, ТО МОЖНО ВЫПИСАТЬ ФОРМУЛЫ, КОТОРЫМИ ОПРЕДЕЛЯЮТСЯ ПРОИЗВОДЯЩИЕ 
ФУНКЦИИ ДЛЯ РАСПРЕДЕЛЕНИЙ ВЕРОЯТНОСТЕЙ ВЕЛИЧИН~$A$, $B$,~\dots, $X$ 
(СМ.~УПР.~22). нО ДЛЯ ПРОСТОТЫ МЫ ИЗУЧИМ ЗДЕСЬ ТОЛЬКО \emph{СРЕДНИЕ 
ЗНАЧЕНИЯ} ЭТИХ ВЕЛИЧИН~$A_N$, $B_N$,~\dots, $X_N$ КАК ФУНКЦИИ ОТ~$N$. 
рАССМОТРИМ, НАПРИМЕР, СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ~$C_N$, ВЫПОЛНЕННЫХ В 
ПРОЦЕССЕ РАЗДЕЛЕНИЯ. еСЛИ~$N\le M$, ТО~$C_N=0$. пРИ~$N>M$, ТАК КАК ЛЮБОЕ 
ДАННОЕ ЗНАЧЕНИЕ~$s$ ВСТРЕЧАЕТСЯ С ВЕРОЯТНОСТЬЮ~$1/N$,
$$
\eqalignno{
C_N&={1\over N}\sum_{1\le s \le N} (N+1-\delta_{s1}+C_{s-1}+C_{N-s})=\cr
   &=N+1-{1\over N}+{2\over N}\sum_{0\le k < N} C_k. & (18) \cr
}
$$
аНАЛОГИЧНЫЕ ФОРМУЛЫ ИМЕЮТ МЕСТО И ДЛЯ ОСТАЛЬНЫХ ВЕЛИЧИН~$A_N$, $B_N$,~\dots, 
$X_N$ (СМ.~УПР.~23).
%% 148

сУЩЕСТВУЕТ ПРОСТОЙ СПОСОБ РЕШЕНИЯ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ ВИДА
$$
x_n=f_n+{2\over n}\sum_{0\le k < n} x_k \rem{ПРИ $n\ge m$.}
\eqno(19)
$$
нА ПЕРВОМ ШАГЕ ОСВОБОЖДАЮТСЯ ОТ ЗНАКА СУММИРОВАНИЯ: ПОСКОЛЬКУ
$$
\eqalign{
(n+1)x_{n+1}&=(n+1)f_{n+1}+2\sum_{0\le k \le n} x_k, \cr
      n x_n &=nf_n+2\sum_{0\le k<n} x_k,\cr
}
$$
ТО МОЖНО ВЫЧЕСТЬ ВТОРОЕ РАВЕНСТВО ИЗ ПЕРВОГО, ПОЛУЧИВ
$$
(n+1)x_{n+1}-nx_n=g_n+2x_n, \rem{ГДЕ $g_n=(n+1)f_{n+1}-nf_n$.}
$$
тЕПЕРЬ РЕКУРРЕНТНАЯ ЗАВИСИМОСТЬ ПРИНИМАЕТ ГОРАЗДО БОЛЕЕ ПРОСТОЙ ВИД:
$$
(n+1)x_{n+1}=(n+2)x_n+g_n \rem{ПРИ $n\ge m$.}
\eqno(20)
$$
\emph{лЮБОЕ} РЕКУРРЕНТНОЕ СООТНОШЕНИЕ ОБЩЕГО ВИДА
$$
a_n x_{n+1}=b_n x_n + g_n
\eqno(21)
$$
МОЖНО СВЕСТИ К ПРОСТОЙ СУММЕ, ЕСЛИ УМНОЖИТЬ ОБЕ ЧАСТИ НА СУММИРУЮЩИЙ 
МНОЖИТЕЛЬ~$a_0a_1\ldots{}a_{n-1}/b_0b_1\ldots{}b_n$. пОЛУЧАЕМ
$$
y_{n+1}=y_n+c_n, 
\rem{ГДЕ $\displaystyle y_n={a_0\ldots a_{n-1}\over b_0\ldots b_{n-1}}x_n$,
$\displaystyle c_n={a_0\ldots a_{n-1}\over b_0\ldots b_n}g_n$.}
\eqno(22)
$$
в СЛУЧАЕ~(20) СУММИРУЮЩИЙ МНОЖИТЕЛЬ РАВЕН ПРОСТО~$n!/(n+2)!=1/(n+1)(n+2)$. 
тАКИМ ОБРАЗОМ, НАХОДИМ, ЧТО ПРОСТОЕ СООТНОШЕНИЕ
$$
{x_{n+1}\over n+2}={x_n \over n+1}+{(n+1)f_{n+1}-nf_n \over (n+1)(n+2)},
\rem{$n\ge m$,}
\eqno(23)
$$
ЯВЛЯЕТСЯ СЛЕДСТВИЕМ СООТНОШЕНИЯ~(19).

еСЛИ, НАПРИМЕР, ПОЛОЖИТЬ~$f_n=1/n$, ТО ПОЛУЧИТСЯ НЕОЖИДАННЫЙ 
РЕЗУЛЬТАТ~$x_n/(n+1)=x_m/(m+1)$ ПРИ ЛЮБОМ~$n\ge m$. 
еСЛИ ПОЛОЖИТЬ~$f_n=n+1$, ТО ПОЛУЧИТСЯ
$$
\eqalign{
x_n/(n+1)&=2/(n+1)+2/n+\cdots+2/(m+2)+x_m/(m+1)=\cr
         &=2(H_{n+1}-H_{m+1})+x_m/(m+1)\cr
}
$$
ПРИ ЛЮБОМ~$n\ge m$. кОМБИНАЦИЯ ЭТИХ ДВУХ РЕШЕНИЙ И ПОДСТАНОВКА~$m=M+1$ 
И~$x_n=0$ ПРИ~$n\le M$ ДАЮТ ФОРМУЛУ
$$
\eqalignno{
C_N&=(N+1)\left(2H_{N+1}-2H_{M+2}+1-{1\over (M+1)(M+2)}\right)\approx\cr
&\approx 2(N+1)\ln \left({N+1\over M+2}\right) \rem{ПРИ~$N>M$.} &(24)\cr
}
$$
%% 149
в П.~6.2.2 МЫ ДОКАЖЕМ, ЧТО СТАНДАРТНОЕ ОТКЛОНЕНИЕ 
ВЕЛИЧИНЫ~$C_N$ АСИМПТОТИЧЕСКИ РАВНО~$\sqrt{(21-2\pi^2)}/3N$; ЭТО ДОВОЛЬНО 
МАЛО ПО СРАВНЕНИЮ С~(24).

оСТАЛЬНЫЕ ВЕЛИЧИНЫ МОЖНО НАЙТИ АНАЛОГИЧНЫМ СПОСОБОМ (СМ.~УПР.~23); ИМЕЕМ
$$
\eqalign{
A_N&=2(N+1)/(M+2)-1,\cr
B_N&={1\over 6}(N+1)\left(2H_{N+1}-2H_{M+2}+1-{6\over M+2}\right)+{1\over2},\cr
D_N&=(N+1)M(M-1)/(M+2)(M+1),\cr
E_N&={1\over6}(N+1)M(M-1)/(M+2),\cr
L_N&=4(N+1)/(M+2)(M+1),\cr
X_N&=(N+1)/(M+2)-{1\over2} \rem{ПРИ $N>M$.}\cr
}
\eqno(25)
$$

пРИВЕДЕННОЕ ВЫШЕ ОБСУЖДЕНИЕ ПОКАЗЫВАЕТ, ЧТО МОЖНО ПРОИЗВЕСТИ ТОЧНЫЙ 
АНАЛИЗ СРЕДНЕГО ВРЕМЕНИ ВЫПОЛНЕНИЯ ВЕСЬМА СЛОЖНОЙ ПРОГРАММЫ, ИСПОЛЬЗУЯ 
МЕТОДЫ, КОТОРЫЕ МЫ РАНЕЕ ПРИМЕНЯЛИ ЛИШЬ К БОЛЕЕ ПРОСТЫМ СЛУЧАЯМ.

чТОБЫ ОПРЕДЕЛИТЬ "НАИЛУЧШЕЕ" ЗНАЧЕНИЕ~$M$ ДЛЯ КОНКРЕТНОЙ МАШИНЫ, МОЖНО 
ВОСПОЛЬЗОВАТЬСЯ ФОРМУЛАМИ~(24) И~(25). пРОГРАММА~Q ДЛЯ МАШИНЫ~\MIX{} 
ТРЕБУЕТ $37A+14B+4C+12D+8E-L+8X+15$~ЕДИНИЦ ВРЕМЕНИ; ЭТО РАВНО В СРЕДНЕМ
${1\over3}(38(N+1)H_N+(N+1)f(M))-19$~ЕДИНИЦ ПРИ~$N>M$, ГДЕ
$$
f(M)=4M+38H_{M+2}+43+{84\over M+2}+{48\over (M+2)(M+1)}.
\eqno(26)
$$
мЫ ХОТИМ ВЫБРАТЬ ТАКОЕ ЗНАЧЕНИЕ~$M$, ПРИ КОТОРОМ ФУНКЦИЯ~$f(M)$ ДОСТИГАЕТ 
МИНИМУМА. в ДАННОМ СЛУЧАЕ
$$
f(M)-f(M-1)=4-{38\over M+2}-{84\over (M+2)(M+1)}-{96 \over(M+2)(M+1)M},
$$
И ТРЕБУЕТСЯ НАЙТИ ТАКОЕ ЗНАЧЕНИЕ~$M$, ЧТОБЫ~$f(M)-f(M-1)\le 0$,
$f(M+1)-f(M)\ge 0$; РЕШЕНИЕ~$M=9$ НАЙТИ НЕТРУДНО. еСЛИ~$M=9$, ТО ПРИ 
БОЛЬШИХ~$N$ СРЕДНЕЕ ВРЕМЯ ВЫПОЛНЕНИЯ ПРОГРАММЫ~Q РАВНО 
ПРИБЛИЗИТЕЛЬНО~$12.67(N+1)\ln N-1.92N-14.59$.

тАКИМ ОБРАЗОМ, ПРОГРАММА~Q РАБОТАЕТ В СРЕДНЕМ ДОВОЛЬНО БЫСТРО; СЛЕДУЕТ, 
КРОМЕ ТОГО, УЧЕСТЬ, ЧТО ОНА ТРЕБУЕТ ОЧЕНЬ МАЛО ПАМЯТИ. нО КАКОВ 
\emph{НАИХУДШИЙ} СЛУЧАЙ ДЛЯ АЛГОРИТМА~Q? сУЩЕСТВУЮТ ЛИ КАКИЕ-НИБУДЬ 
ИСХОДНЫЕ ФАЙЛЫ, ОБРАБАТЫВАТЬ КОТОРЫЕ ЭТИМ АЛГОРИТМОМ НЕ ЭФФЕКТИВНО? оТВЕТ 
НЕСКОЛЬКО ОБЕСКУРАЖИВАЕТ: ЕСЛИ ИСХОДНЫЙ ФАЙЛ УЖЕ УПОРЯДОЧЕН, А 
ИМЕННО~$K_1<K_2<\ldots<K_N$, ТО КАЖДАЯ ОПЕРАЦИЯ "РАЗДЕЛЕНИЯ" СТАНОВИТСЯ 
ПОЧТИ БЕСПОЛЕЗНОЙ, ТАК КАК ПОДФАЙЛ СВОДИТСЯ К ОДНОМУ ЭЛЕМЕНТУ! зНАЧИТ, В 
ЭТОЙ СИТУАЦИИ (КОТОРАЯ ДОЛЖНА БЫТЬ САМОЙ ПРОСТОЙ
%% 150
\bye