\input style
%% 188

pUSTX $s_l$---RAZMER PODDEREVA S KORNEM~$l$, 
A~$M_N$---MULXTIMNOZHESTVO~$\{s_1, s_2, \ldots, s_N\}$ VSEH |TIH RAZMEROV. 
iSPOLXZUYA (14) I (15), LEGKO VYCHISLITX~$M_N$ PRI LYUBOM ZADANNOM~$N$. v 
UPR.~5.1.4--20 POKAZANO, CHTO OBSHCHEE CHISLO SPOSOBOV POSTROITX PIRAMIDU 
IZ CELYH CHISEL $\{1, 2, \ldots, N\}$ RAVNO
$$
N!/s_1s_2\ldots s_N= N!/\prod_{s\in M_N} s.
\eqno(16)
$$
nAPRIMER, CHISLO SPOSOBOV RASPOLOZHITX 26 BUKV $\{A, B, C, \ldots, Z\}$ NA 
RIS.~28 TAK, CHTOBY PO VERTIKALI SOHRANYALSYA ALFAVITNYJ PORYADOK, RAVNO
$$
26!/(26 \cdot 10 \cdot 6 \cdot 2 \cdot 1 \cdot 1^{12} \cdot 3^6 \cdot 7^2 
\cdot 15^1).
$$

tEPERX MY V SOSTOYANII PROANALIZIROVATX FAZU POSTROENIYA PIRAMIDY V 
ALGORITME~H, T. E. VYCHISLENIYA, KOTORYE ZAVERSHAYUTSYA DO TOGO, KAK V SHAGE H2 
VPERVYE VYPOLNITSYA USLOVIE $l=1$. k SCHASTXYU, BLAGODARYA SLEDUYUSHCHEJ NIZHE 
TEOREME ANALIZ POSTROENIYA PIRAMIDY MOZHNO SVESTI K IZUCHENIYU NEZAVISIMYH OPERACIJ PROTASKIVANIYA.

\proclaim tEOREMA H. eSLI ISHODNYMI DANNYMI DLYA ALGORITMA H 
SLUZHIT SLUCHAJNAYA PERESTANOVKA MNOZHESTVA $\{ 1, 2, \ldots, N\}$, TO V 
FAZE POSTROENIYA PIRAMIDY S ODINAKOVOJ VEROYATNOSTXYU MOZHET POLUCHITXSYA 
LYUBAYA IZ $N! /\left(\prod_{s\in M_N} s\right)$ VOZMOZHNYH PIRAMID. bOLEE 
moGO,
VSE $\floor{N/2}$ OPERACIJ PROTASKIVANIYA, VYPOLNENNYE ZA VREMYA |TOJ FAZY, 
"RAVNOMERNY" V TOM SMYSLE, CHTO PO DOSTIZHENII SHAGA H8 VSE $s_l$ VOZMOZHNYH 
ZNACHENIJ PEREMENNOJ~$i$ RAVNOVEROYATNY.

\proof pRIMENIM METOD, KOTORYJ V CHISLENNOM ANALIZE NAZYVAETSYA METODOM 
"OBRATNOJ ZADACHI". pUSTX V KACHESTVE ODNOGO IZ VOZMOZHNYH REZULXTATOV 
OPERACII PROTASKIVANIYA ZADANA PIRAMIDA $K_1$ \dots{} $K_N$ S KORNEM V 
UZLE~$l$; TOGDA YASNO, CHTO IMEETSYA VSEGO~$s_l$ ISHODNYH KONFIGURACIJ $K'_1$ 
\dots{} $K'_N$ FAJLA, KOTORYE POSLE PROTASKIVANIYA DAYUT TAKOJ REZULXTAT. 
vSE |TI ISHODNYE KONFIGURACII IMEYUT RAZLICHNYE ZNACHENIYA $K'_l$, 
SLEDOVATELXNO, RASSUZHDAYA V OBRATNOM NAPRAVLENII, SUSHCHESTVUET ROVNO $s_l$ 
$s_{l+1}$ \dots{} $s_N$ ISHODNYH PERESTANOVOK MNOZHESTVA 
$\{1, 2, \ldots, N\}$, KOTORYE POSLE ZAVERSHENIYA OPERACII PROTASKIVANIYA V 
POZICIYU~$l$ DAYUT KONFIGURACIYU $K_1$ \dots{} $K_N$.

sLUCHAJ $l=1$ TIPICHEN: PUSTX $K_1$ \dots{} $K_N$---PIRAMIDA, I PUSTX $K'_1$ 
\dots{} $K'_N$---FAJL, KOTORYJ PREOBRAZUETSYA V $K_1$ \dots{} $K_N$ V 
REZULXTATE PROTASKIVANIYA PRI $l=1$, $K=K'_1$. eSLI $K=K_i$, TO DOLZHNY
IMETX MESTO RAVENSTVA $K'_i=K_{\floor{i/2}}$, 
$K'_{\floor{i/2}}=K_{\floor{i/4}}$ I T. D., PRI |TOM $K'_j=K_j$ DLYA VSEH 
$j$, NE LEZHASHCHIH NA PUTI OT~$1$ K~$i$. oBRATNO, PRI LYUBOM~$i$ V REZULXTATE 
TAKOGO POSTROENIYA POLUCHAETSYA FAJL $K'_1$ \dots{} $K'_N$, TAKOJ, CHTO (a) 
OPERACIYA PROTASKIVANIYA PREOBRAZUET
%% 189
FAJL $K'_1$ \dots{} $K'_N$ V $K_1$ \dots{} $K_N$ I 
(b) $K_{\floor{j/2}}\ge K_j$ PRI $2 \le \floor{j/2}<j\le N$. 
sLEDOVATELXNO, VOZMOZHNY ROVNO~$N$ 
TAKIH FAJLOV $K'_1$ \dots{} $K'_N$,  I OPERACIYA PROTASKIVANIYA RAVNOMERNA. 
(pRIMER DOKAZATELXSTVA |TOJ TEOREMY SM. V UPR.~22.)\proofend

oBRASHCHAYASX K VELICHINAM $A$, $B$, $C$, $D$ V ANALIZE PROGRAMMY~H, MOZHNO 
VIDETX, CHTO RAVNOMERNAYA OPERACIYA PROTASKIVANIYA, PROIZVODIMAYA NAD 
PODDEREVOM RAZMERA~$s$, DAET VKLAD $\floor{s/2}/s$ V SREDNEE ZNACHENIE 
VELICHINY~$A$; EE VKLAD V SREDNEE ZNACHENIE VELICHINY~$B$ RAVEN
$$
{1\over s}(0+1+1+2+\cdots+\floor{\log_2 s})=
{1\over s}\left(\sum_{1\le k\le s} \floor{\log_2 k}\right)=
{1\over s}((s+1)\floor{\log_2 s}-2^{\floor{\log_2 s}+1}+2)
$$
(SM. UPR. 1.2.4--42); I ONA DAET VKLAD~$2/s$ ILI~$0$ V SREDNEE ZNACHENIE 
VELICHINY~$D$ V ZAVISIMOSTI OT TOGO, YAVLYAETSYA LI~$s$ CHETNYM ILI NECHETNYM. 
nESKOLXKO SLOZHNEE OPREDELITX SOOTVETSTVUYUSHCHIJ VKLAD V SREDNEE ZNACHENIE 
VELICHINY~$C$, TAK CHTO |TA ZADACHA PREDOSTAVLYAETSYA CHITATELYU (SM. UPR.~26). 
pROIZVODYA SUMMIROVANIE PO VSEM OPERACIYAM PROTASKIVANIYA, NAHODIM, CHTO 
SREDNEE ZNACHENIE VELICHINY~$A$ ZA VREMYA POSTROENIYA PIRAMIDY RAVNO
$$
A'_N=\sum_{s\in M_N} \floor{s/2}/s;
\eqno(17)
$$
ANALOGICHNYE FORMULY IMEYUT MESTO I DLYA~$B$, $C$ I~$D$, TAK CHTO MOZHNO BEZ 
OSOBOGO TRUDA TOCHNO VYCHISLITX |TI SREDNIE ZNACHENIYA. v SLEDUYUSHCHEJ TABLICE 
PRIVEDENY TIPICHNYE REZULXTATY:
\ctable{
\hfill\bskip$#$\bskip&&\hfill\bskip$#$\bskip\cr
N\hfill & A'_N\hfill & B'_N\hfill& C'_N\hfill & D'_N \hfill\cr
  99 &  19.18 &  68.35 &  42.95 & 0.00 \cr
  100&  19.93 &  69.39 &  42.71 & 1.84 \cr
  999&  196.16& 734.66 & 464.53 & 0.00 \cr
 1000&  196.94& 735.80 & 464.16 & 1.92 \cr
 9999& 1966.02& 7428.18&4695.54 & 0.00 \cr
10000& 1966.82& 7429.39&4695.06 & 1.97 \cr
10001& 1966.45& 7430.07&4695.84 & 0.00 \cr
10002& 1967.15& 7430.97& 4695.95& 1.73 \cr
}
chTO KASAETSYA ASIMPTOTIKI, TO V~$M_N$ MOZHNO NE OBRASHCHATX VNIMANIYA NA 
RAZMERY OSOBYH PODDEREVXEV, I TOGDA MY NAJDEM, NAPRIMER, CHTO
$$
A'_N={N\over 2}\cdot{0\over1}+{N\over 4}\cdot{1\over3}+
{N\over8}\cdot{3\over7}+\cdots+O(\log N)=
\left(1-{1\over2}\alpha\right)N+O(\log N),
\eqno(18)
$$
%% 190
GDE
$$
\alpha=\sum_{k\ge 1} {1\over 2^k-1}=
1.60669\ 51524\ 15291\ 76378\ 33015\ 23190\ 92458\ 04805\hbox{---}.
\eqno  (19)
$$
(eTO ZNACHENIE POLUCHIL dZH.~u.~rENCH MLADSHIJ, POLXZUYASX PREOBRAZOVANIEM 
RYADA IZ UPR.~27.) pRI BOLXSHIH~$N$ MOZHNO ISPOLXZOVATX PRIBLIZHENNYE FORMULY
$$
\eqalign{
A'_N&\approx 0.1967N+0.3 \hbox{ ($N$ CHET.)}, 
  \quad 0.1967N-0.3 \hbox{($N$ NECHET.)};\cr
B'_N&\approx 0.74403N-1.3\ln N;\cr
C'_N&\approx 0.47034N-0.8\ln N;\cr
D'_N&\approx 1.8 \pm 0.2 \hbox{ ($N$ CHET.)},
  \quad 0 \hbox{($N$ NECHET.)}.\cr
}
\eqno(20)
$$
nETRUDNO OPREDELITX TAKZHE MAKSIMALXNYE I MINIMALXNYE ZNACHENIYA. dLYA 
POSTROENIYA PIRAMIDY TREBUETSYA VSEGO $O(N)$ SHAGOV (SR. S UPR.~23).

eTIM, PO SUSHCHESTVU, ZAVERSHAETSYA ANALIZ FAZY POSTROENIYA PIRAMIDY V 
ALGORITME~H. aNALIZ FAZY VYBORA---SOVSEM DRUGAYA ZADACHA, KOTORAYA ESHCHE OZHIDAET 
SVOEGO RESHENIYA! pUSTX PIRAMIDALXNAYA SORTIROVKA PRIMENYAETSYA K 
$N$~|LEMENTAM; OBOZNACHIM CHEREZ $A''_N$, $B''_N$, $C''_N$ I~$D''_N$ SREDNIE 
ZNACHENIYA VELICHIN $A$, $B$, $C$ I~$D$ VO VREMYA FAZY VYBORA. pOVEDENIE 
ALGORITMA~H PODVERZHENO SRAVNITELXNO MALYM KOLEBANIYAM OKOLO |MPIRICHESKI 
USTANOVLENNYH SREDNIH ZNACHENIJ
$$
\eqalign{
A''_N &\approx 0.152N;\cr
B''_N &\approx N\log_2N-2.61N;\cr
C''_N &\approx {1\over2}N\log_2N-1.4N;\cr
D''_N &\approx \ln N\pm 2;\cr
}
\eqno(21)
$$
TEM NE MENEE DO SIH POR NE NAJDENO PRAVILXNOGO TEORETICHESKOGO OB�YASNENIYA 
|TIM KONSTANTAM. rASSMOTREV OTDELXNYE OPERACII PROTASKIVANIYA, NETRUDNO 
VYVESTI VERHNIE OCENKI, UKAZANNYE V NERAVENSTVAH (8), HOTYA, ESLI 
RASSMATRIVATX ALGORITM KAK CELOE, VERHNYUYU OCENKU DLYA~$C$, PO-VIDIMOMU, 
SLEDUET UMENXSHITX
PRIBLIZITELXNO DO~${1\over 2}N\log_2 N$.

\excercises
\ex[10] yaVLYAETSYA LI SORTIROVKA POSREDSTVOM PROSTOGO VYBORA (ALGORITM S) 
"USTOJCHIVOJ"?

\ex[15] pOCHEMU V ALGORITME S OKAZYVAETSYA BOLEE UDOBNYM NAHODITX SNACHALA 
NAIBOLXSHIJ |LEMENT, ZATEM NAIBOLXSHIJ IZ OSTAVSHIHSYA I T. D , VMESTO TOGO 
CHTOBY NAHODITX SNACHALA NAIMENXSHIJ |LEMENT, ZATEM NAIMENXSHIJ IZ 
OSTAVSHIHSYA I T. D.?

%% 191
\ex[m21] (a) dOKAZHITE, CHTO ESLI ALGORITM S PRIMENYAETSYA K 
SLUCHAJNOJ PERESTANOVKE MNOZHESTVA $\{1, 2, \ldots, N\}$, TO V REZULXTATE 
PERVOGO VYPOLNENIYA SHAGOV~S2 I~S3 POLUCHAETSYA SLUCHAJNAYA PERESTANOVKA 
MNOZHESTVA $\{1, 2, \ldots, N-1\}$, ZA KOTOROJ SLEDUET~$N$. (iNACHE GOVORYA, 
FAJL $K_1$ \dots{} $K_{N-1}$ S ODINAKOVOJ VEROYATNOSTXYU MOZHET BYTX LYUBOJ 
PERESTANOVKOJ MNOZHESTVA $\{1, 2, \ldots, N-1\}$.) (b) sLEDOVATELXNO, ESLI 
CHEREZ $B_N$ OBOZNACHITX SREDNEE ZNACHENIE VELICHINY~$B$ V PROGRAMME~S, TO PRI 
USLOVII, CHTO ISHODNYJ FAJL UPORYADOCHEN SLUCHAJNYM OBRAZOM, 
IMEEM~$B_N=H_N-1+B_{N-1}$. [\emph{uKAZANIE:} SR. SO 
STATISTICHESKIMI HARAKTERISTIKAMI 1.2.10--16.]

\rex[m35] v SHAGE~S3 ALGORITMA~S NICHEGO NE DELAETSYA, ESLI $i=j$. He 
LUCHSHE LI PERED VYPOLNENIEM SHAGA~S3 PROVERITX USLOVIE~$i=j$? chEMU RAVNO 
SREDNEE CHISLO SLUCHAEV VYPOLNENIYA USLOVIYA $i=j$ V SHAGE~S3, ESLI ISHODNYJ FAJL 
SLUCHAEN?

\ex[20] chEMU RAVNO ZNACHENIE VELICHINY~$B$ V ANALIZE PROGRAMMY~S 
DLYA ISHODNOGO FAJLA $N \ldots 3\ 2\ 1$?

\ex[m29] (a) pUSTX $a_1$ $a_2$~\dots{} $a_N$---PERESTANOVKA MNOZHESTVA $\{1, 
2, \ldots, N\}$ S~$C$ CIKLAMI, $I$~INVERSIYAMI I TAKAYA, CHTO PRI EE 
SORTIROVKE S POMOSHCHXYU PROGRAMMY~S PROIZVODITSYA $B$~OBMENOV NA 
PRAVOSTORONNIJ MAKSIMUM. dOKAZHITE, CHTO $2B\le I+N-C$. [\emph{uKAZANIE:} SM.
 UPR.~5.2.2--1.] (b) pOKAZHITE, CHTO~$I+N-C\le\floor{n^2/2}$; SLEDOVATELXNO, 
$B$ NE PREVYSHAET~$\floor{n^2/4}$.

\ex[m46] nAJDITE DISPERSIYU VELICHINY~$B$ V PROGRAMME~S KAK FUNKCIYU OT~$N$, 
SCHITAYA, CHTO ISHODNYJ FAJL SLUCHAEN.

\ex[24] pOKAZHITE, CHTO ESLI PRI POISKE~$\max(K_1, \ldots, K_j)$ V SHAGE S2 
PROSMATRIVATX KLYUCHI SLEVA NAPRAVO: $K_1$, $K_2$, \dots, $K_j$, A NE 
NAOBOROT: $K_j$, \dots, $K_2$, $K_1$, KAK V PROGRAMME~S, TO ZA SCHET |TOGO 
MOZHNO BYLO BY SOKRATITX CHISLO SRAVNENIJ PRI SLEDUYUSHCHIH POVTORENIYAH 
SHAGA~S2. nAPISHITE \MIX-PROGRAMMU, OSNOVANNUYU NA |TOM NABLYUDENII.

\ex[m25] chEMU RAVNO SREDNEE CHISLO SRAVNENIJ, VYPOLNYAEMYH ALGORITMOM IZ 
UPR.~8 DLYA SLUCHAJNOGO ISHODNOGO FAJLA?

\ex[12] kAK BUDET VYGLYADETX DEREVO, IZOBRAZHENNOE NA RIS.~23, POSLE TOGO 
KAK BUDUT VYVEDENY~14 IZ~16 PERVONACHALXNYH |LEMENTOV?

\ex[10] kAK BUDET VYGLYADETX DEREVO, IZOBRAZHENNOE NA RIS.~24, POSLE VYVODA 
|LEMENTA~$908$?

\ex[m20] sKOLXKO RAZ BUDET VYPOLNENO SRAVNENIE~$-\infty$ S~$\infty$, 
ESLI PRIMENITX "VOSHODYASHCHIJ" METOD, PREDSTAVLENNYJ NA RIS.~23, DLYA 
UPORYADOCHENIYA FAJLA IZ $2^n$~|LEMENTOV?

\ex[20] (dZH.~u.~dZH.~uILXYAME.) v SHAGE~H4 ALGORITMA~H RAZLICHAYUTSYA TRI 
SLUCHAYA: $j<r$, $j=r$ I~$j>r$. pOKAZHITE, CHTO ESLI $K\ge K_{r+1}$, TO 
MOZHNO BYLO BY TAK UPROSTITX SHAG~H4, CHTOBY RAZVETVLENIE PROISHODILO LISHX 
PO DVUM PUTYAM. kAK NADO IZMENITX SHAG~H2, CHTOBY OBESPECHITX V PROCESSE 
PIRAMIDALXNOJ SORTIROVKI VYPOLNENIE USLOVIYA $K\ge K_{r+1}$?

\ex[10] pOKAZHITE, CHTO PROSTAYA OCHEREDX---CHASTNYJ SLUCHAJ 
PRIORITETNOJ. (oB�YASNITE, KAKIE KLYUCHI NUZHNO PRISVAIVATX |LEMENTAM, CHTOBY 
PROCEDURA "NAIBOLXSHIJ IZ VKLYUCHENNYH---PERVYM ISKLYUCHAETSYA" BYLA |KVIVALENTNA 
PROCEDURE "PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA".) yaVLYAETSYA LI STEK 
TAKZHE CHASTNYM SLUCHAEM PRIORITETNOJ OCHEREDI?

\rex[M22] (v.~e.~chARTRS.) pRIDUMAJTE BYSTRYJ ALGORITM POSTROENIYA TABLICY 
PROSTYH CHISEL $\le N$, V KOTOROM ISPOLXZUETSYA \emph{PRIORITETNAYA 
OCHEREDX} S CELXYU IZBEZHATX OPERACIJ DELENIYA. [\emph{uKAZANIE.} pUSTX 
NAIMENXSHIJ KLYUYA V PRIORITETNOJ OCHEREDI BUDET NAIMENXSHIM NECHETNYM NEPROSTYM 
CHISLOM, BOLXSHIM, CHEM SAMOE POSLEDNEE NECHETNOE CHISLO, VOSPRINYATOE KAK 
KANDIDAT V PROSTYE CHISLA. pOPYTAJTESX SVESTI K MINIMUMU CHISLO |LEMENTOV 
V |TOJ OCHEREDI.]

\ex[20] pOSTROJTE |FFEKTIVNYJ ALGORITM, KOTORYJ VSTAVLYAET NOVYJ KLYUCH V 
DANNUYU PIRAMIDU IZ P |LEMENTOV, POROZHDAYA PIRAMIDU IZ $n+1$~|LEMENTOV.

\ex[20] aLGORITM IZ UPR.~16 MOZHNO ISPOLXZOVATX DLYA POSTROENIYA PIRAMIDY 
VZAMEN METODA "UMENXSHENIYA $l$ DO~$1$", PRIMENYAEMOGO V ALGORITME~H.

%%192
pOROZHDAYUT LI OBA METODA IZ ODNOGO I TOGO ZHE ISHODNOGO FAJLA ODNU I TU ZHE PIRAMIDU?

\rex[21] (r.~u.~fLOJD) vO VREMYA FAZY VYBORA V ALGORITME PIRAMIDALXNOJ 
SORTIROVKI KLYUCH $K$, KAK PRAVILO, PRINIMAET DOVOLXNO MALYE ZNACHENIYA, I 
PO|TOMU POCHTI PRI VSEH SRAVNENIYAH V SHAGE H6 OBNARUZHIVAETSYA, CHTO 
$K<K_j$. kAK. MOZHNO IZMENITX ALGORITM, CHTOBY KLYUCH $K$ NE SRAVNIVALSYA 
S~$K_j$ V OSNOVNOM CIKLE VYCHISLENIJ?

\ex[21] pREDLOZHITE ALGORITM ISKLYUCHENIYA DANNOGO |LEMENTA IZ PIRAMIDY 
RAZMERA $N$, POROZHDAYUSHCHIJ PIRAMIDU RAZMERA~$N-1$.

\ex[m20] pOKAZHITE, CHTO FORMULY (14) ZADAYUT RAZMERY OSOBYH PODDEREVXEV PIRAMIDY.

\ex[m24] dOKAZHITE, CHTO FORMULY (15) ZADAYUT RAZMERY NEOSOBYH PODDEREVXEV PIRAMIDY.

\rex[20] kAKIE PERESTANOVKI MNOZHESTVA $\{1, 2, 3, 4, 5\}$ FAZA 
NOSTROENIYA PIRAMIDY V ALGORITME~H PREOBRAZUET V $5\ 3\ 4\ 1\ 2$?

\ex[m28] (a) dOKAZHITE, CHTO DLINA PUTI~$B$ V ALGORITME 
PROTASKIVANIYA NIKOGDA NE PREVYSHAET $\floor{\log_2(r/l)}$. (b) sOGLASNO 
NERAVENSTVAM (8), NI PRI KAKOM KONKRETNOM PRIMENENII ALGORITMA~H 
VELICHINA~$B$ NE MOZHET PREVZOJTI $N\floor{\log_2 N}$. nAJDITE MAKSIMALXNOE 
ZNACHENIE~$B$ PO VSEVOZMOZHNYM ISHODNYM FAJLAM KAK FUNKCIYU OT~$N$. (vY 
DOLZHNY DOKAZATX, CHTO SUSHCHESTVUET ISHODNYJ FAJL, NA KOTOROM~$B$ PRINIMAET 
|TO MAKSIMALXNOE ZNACHENIE.)

\ex[m24] vYVEDITE TOCHNUYU FORMULU STANDARTNOGO OTKLONENIYA 
VELICHINY~$B'_N$ (SUMMARNAYA DLINA PUTI, PROJDENNOGO PO DEREVU VO VREMYA FAZY 
POSTROENIYA PIRAMIDY V ALGORITME~H).

\ex[m20] chEMU RAVEN SREDNIJ VKLAD V ZNACHENIE VELICHINY~$C$ ZA VREMYA PERVOJ 
OPERACII PROTASKIVANIYA, KOGDA $l=1$, a $r=N$, ESLI~$N=2^{n+1}-1$.

\ex[m30] rESHITE UPR.~25:  (a) DLYA $N =26$, (b) DLYA PROIZVOLXNOGO~$N$.

\ex[m25] (dZH.~u.~rENCH~ML.) dOKAZHITE, CHTO 
$\sum_{n\ge 1} x^n/(1-x^n)=\sum_{n\ge 1} x^{n^2}(1+x^n)/(1-x^n)$. [pOLOZHIV 
$x={1\over2}$, POLUCHITE OCHENX BYSTRO SHODYASHCHIJSYA RYAD DLYA VYCHISLENIYA (19). )

\ex[35] pRODUMAJTE IDEYU \emph{TERNARNYH PIRAMID}, OSNOVANNYH NA 
POLNYH TERNARNYH, A NE BINARNYH DEREVXYAH. bUDET LI TERNARNAYA PIRAMIDALXNAYA 
SORTIROVKA BYSTREE BINARNOJ?

\ex[26] (u. s. bRAUN.) pOSTROJTE ALGORITM UMNOZHENIYA MNOGOCHLENOV 
ILI STEPENNYH 
RYADOV~$(a_1x^{i_1}+a_2x^{i_2}+\cdots)(b_1x^{j_1}+b_2x^{j_2}+\cdots)$, 
KOTORYJ BY POROZHDAL KO|FFICIENTY PROIZVEDENIYA $c_1x^{i_1+j_1}+\cdots$ PO 
PORYADKU, PO MERE TOGO KAK PEREMNOZHAYUTSYA KO|FFICIENTY ISHODNYH 
MNOGOCHLENOV. [\emph{uKAZANIE:} 'VOSPOLXZUJTESX PODHODYASHCHEJ PRIORITETNOJ OCHEREDXYU.]

\ex[m48] mOZHET LI VELICHINA~$C$ PREVZOJTI ${1\over2}N\log_2 N$ PRI 
PIRAMIDALXNOJ SORTIROVKE FAJLA? chEMU RAVNO MAKSIMALXNOE ZNACHENIE~$C$? 
chEMU RAVNO MINIMALXNOE ZNACHENIE?

\ex[37] (dZH.~u.~dZH.~uILXYAME.) pOKAZHITE, CHTO ESLI DVE PIRAMIDY PODHODYASHCHIM 
OBRAZOM SOVMESTITX "OSNOVANIE K OSNOVANIYU", TO |TO DAST 
VOZMOZHNOSTX PODDERZHIVATX STRUKTURU, V KOTOROJ V LYUBOJ MOMENT MOZHNO ZA 
$O(\log n)$~SHAGOV ISKLYUCHITX LIBO NAIBOLXSHIJ, LIBO NAIMENXSHIJ |LEMENT. 
(tAKUYU STRUKTURU MOZHNO NAZVATX \emph{PRIORITETNYM DEKOM}.)


\ex[21] rAZRABOTAJTE ALGORITM SLIYANIYA DVUH NEPERESEKAYUSHCHIHSYA PRIORITETNYH 
OCHEREDEJ, PREDSTAVLENNYH V VIDE LEVOSTORONNIH DEREVXEV, V ODNU. (v 
CHASTNOSTI, ESLI ODNA IZ DANNYH OCHEREDEJ SODERZHIT VSEGO ODIN |LEMENT, TO 
VASH ALGORITM BUDET VSTAVLYATX EGO V DRUGUYU OCHEREDX.) 

\rex[15] pOCHEMU V PRIORITETNOJ OCHEREDI, PREDSTAVLENNOJ V VIDE 
LEVOSTORONNEGO DEREVA, OPERACIYA UDALENIYA KORNYA VYPOLNYAETSYA PUTEM SLIYANIYA
%% 193
DVUH PODDEREVXEV, A NE "PRODVIZHENIYA" UZLOV PO NAPRAVLENIYU K VERSHINE, KAK V PIRAMIDE?

\ex[m47] sKOLXKO MOZHNO POSTROITX LEVOSTORONNIH DEREVXEV IZ $N$~UZLOV, ESLI 
IGNORIROVATX ZNACHENIYA POLYA~|KEY|? [eTA POSLEDOVATELXNOSTX NACHINAETSYA S 
CHISEL $1$, $1$, $2$, $4$, $8$, $17$, $38$, \dots; SUSHCHESTVUET LI 
KAKAYA-NIBUDX PROSTAYA ASIMPTOTICHESKAYA FORMULA?]

\ex[26] eSLI V LEVOSTORONNEE DEREVO S~$N$ UZLAMI DOBAVITX SVYAZI |UP| (SR. 
S OBSUZHDENIEM DEREVXEV S TREMYA SVYAZYAMI V P.~6.2.3), TO |TO DAST 
VOZMOZHNOSTX ISKLYUCHATX IZ PRIORITETNOJ OCHEREDI PROIZVOLXNYJ UZEL~|P| 
SLEDUYUSHCHIM OBRAZOM: SLITX |LEFT(P)| I~|RIGHT(P)| I POMESTITX POLUCHENNOE 
PODDEREVO NA MESTO~|P|, ZATEM ISPRAVLYATX POLYA~|DIST| U PREDKOV UZLA~|P| DO 
TEH POR, POKA NE BUDET DOSTIGNUT LIBO KORENX, LIBO UZEL, U KOTOROGO 
POLE~|DIST| NE MENYAETSYA.

dOKAZHITE, CHTO PRI |TOM NIKOGDA NE POTREBUETSYA IZMENITX BOLEE CHEM $O(\log 
N)$ POLEJ~|DIST|, NESMOTRYA DAZHE NA TO, CHTO DEREVO MOZHET SODERZHATX. OCHENX 
DLINNYE VOSHODYASHCHIE PUTI.

\ex[18] \emph{(zAMESHCHENIE NAIBOLEE DAVNO ISPOLXZOVANNOJ STRANICY.)} 
mNOGIE OPERACIONNYE SISTEMY ISPOLXZUYUT ALGORITM SLEDUYUSHCHEGO TIPA: NAD 
NABOROM UZLOV DOPUSTIMY DVE OPERACII---"ISPOLXZOVANIE" UZLA I ZAMESHCHENIE 
NAIBOLEE DAVNO "ISPOLXZOVANNOGO" UZLA NOVYM UZLOM. kAKAYA STRUKTURA DANNYH 
OBLEGCHAET NAHOZHDENIE NAIBOLEE DAVNO "ISPOLXZOVANNOGO" UZLA?

\subsubchap{sORTIROVKA SLIYANIEM} %5.2.4
\dfn{sLIYANIE} OZNACHAET OB�EDINENIE DVUH ILI BOLEE UPORYADOCHENNYH FAJLOV V 
ODIN UPORYADOCHENNYJ FAJL. mOZHNO, NAPRIMER, SLITX DVA PODFAJLA---$503\ 703\ 
765$ I~$087\ 512\ 677$, 
POLUCHIV~$087\ 503\ 512\ 677\ 703\ 765$. pROSTOJ SPOSOB SDELATX 
|TO---SRAVNITX DVA NAIMENXSHIH |LEMENTA, VYVESTI NAIMENXSHIJ IZ NIH I 
POVTORITX |TU PROCEDURU.

nACHAV S
$$
\left\{\matrix{
 503 & 703 & 765 \cr
 087 & 512 & 677\cr
}\right.,
$$
POLUCHIM
$$
087\left\{\matrix{
503 & 703 & 765\cr
512 & 677 \cr
}\right.
$$
ZATEM
$$
087\ 503\ \left\{\matrix{
703 & 765\cr
512 & 677\cr
}\right.
$$
I~T.~D. nEOBHODIMO POZABOTITXSYA O DEJSTVIYAH NA SLUCHAJ, KOGDA ISCHERPAETSYA 
ODIN IZ FAJLOV. vESX PROCESS PODROBNO OPISAN V SLEDUYUSHCHEM ALGORITME.
\alg m.(dVUHPUTEVOE SLIYANIE.) eTOT ALGORITM OSUSHCHESTVLYAET SLIYANIE DVUH 
UPORYADOCHENNYH FAJLOV $x_1\le x_2\le\ldots\le x_m$ 
I~$y_1\le y_2 \le \ldots\le y_n$ V ODIN FAJL 
$z_1\le z_2\le \ldots\le z_{m+n}$.
\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $i\asg 1$, $j\asg 1$, $k\asg 1$.
\st[nAJTI NAIMENXSHIJ |LEMENT.] eSLI $x_i\le y_j$, TO PEREJTI K 
SHAGU~\stp{3}; V PROTIVNOM SLUCHAE PEREJTI K~\stp{5}.
%%194
\st[vYVESTI $x_i$.] uSTANOVITX $z_k\asg x_i$,  $k\asg k+1$,  $i\asg i+1$. 
eSLI~$i\le m$, TO VOZVRATITXSYA K \stp{2}.

\st[vYVESTI $y_j, \dots, y_n$.] uSTANOVITX 
$(z_k, \ldots, z_{m+n})\asg(y_j, \ldots, y_n)$ I ZAVERSHITX RABOTU ALGORITMA.

\st[vYVESTI $y_j$.] uSTANOVITX $z_k\asg y_j$, $k\asg k+1$, $j\asg j+1$.  
eSLI $j\le n$, TO VOZVRATITXSYA K \stp{2}.
\st[vYVESTI $x_i$, \dots, $x_m$.] uSTANOVITX 
$(z_k, \ldots, z_{m+n})\asg(x_i, \ldots, x_m)$ I ZAVERSHITX RABOTU ALGORITMA.
\algend
\picture{rIS. 29. sLIYANIE $x_1\le \ldots\le x_m$ S $y_1\le\ldots\le y_n$.}

v P.~5.3.2 MY UVIDIM, CHTO |TA PROSTAYA PROCEDURA, PO SUSHCHESTVU, "NAILUCHSHIJ 
IZ VOZMOZHNYH" SPOSOBOV SLIYANIYA NA TRADICIONNOJ evm, ESLI $m\approx n$. 
(nO, ESLI $m$ GORAZDO MENXSHE $n$, MOZHNO RAZRABOTATX BOLEE |FFEKTIVNYE 
ALGORITMY SORTIROVKI, HOTYA V OBSHCHEM SLUCHAE ONI DOVOLXNO SLOZHNY.) aLGORITM~M 
BEZ OSOBOJ POTERI |FFEKTIVNOSTI MOZHNO NEMNOGO UPROSTITX, DOBAVIV V 
KONEC ISHODNYH FAJLOV ISKUSSTVENNYH "STRAZHEJ" $x_{m+1}=y_{n+1}=\infty$ 
I OSTANAVLIVAYASX PERED VYVODOM~$\infty$. aNALIZ ALGORITMA~M SM. V UPR.~2.

oBSHCHIJ OB�EM RABOTY, VYPOLNYAEMOJ ALGORITMOM~M, PO SUSHCHESTVU, 
PROPORCIONALEN $m+n$, PO|TOMU YASNO, CHTO SLIYANIE---BOLEE PROSTAYA ZADACHA, CHEM 
SORTIROVKA. oDNAKO ZADACHU SORTIROVKI MOZHNO SVESTI K SLIYANIYAM, SLIVAYA VSE 
BOLEE DLINNYE PODFAJLY DO TEH POR, POKA NE BUDET OTSORTIROVAN VESX FAJL. 
tAKOJ PODHOD MOZHNO RASSMATRIVATX KAK RAZVITIE IDEI SORTIROVKI VSTAVKAMI: 
VSTAVKA NOVOGO |LEMENTA V UPORYADOCHENNYJ FAJL---CHASTNYJ SLUCHAJ SLIYANIYA PRI 
$n=1!$ eSLI NUZHNO USKORITX PROCESS VSTAVOK, TO MOZHNO RASSMOTRETX VSTAVKU 
NESKOLXKIH |LEMENTOV ZA RAZ, "GRUPPIRUYA" IH, A |TO ESTESTVENNYM OBRAZOM 
PRIVODIT K OBSHCHEJ IDEE SORTIROVKI SLIYANIEM. s ISTORICHESKOJ TOCHKI ZRENIYA 
METOD SLIYANIJ--- ODIN IZ SAMYH PERVYH METODOV, PREDNAZNACHENNYH DLYA SORTIROVKI
%% 195
\picture{tABLICA 1 sORTIROVKA ESTESTVENNYM DVUHPUTEVYM SLIYANIEM}
NA evm; ON BYL PREDLOZHEN dZHONOM FON nEJMANOM ESHCHE V 1945~G. (SM. \S~5.5).

mY DOVOLXNO PODROBNO IZUCHIM SLIYANIYA V \S~5.4 V SVYAZI S ALGORITMAMI VNESHNEJ 
SORTIROVKI, A V NASTOYASHCHEM PUNKTE SOSREDOTOCHIM SVOE VNIMANIE NA 
SORTIROVKE V BYSTROJ PAMYATI S PROIZVOLXNYM DOSTUPOM.

tABLICA~1 ILLYUSTRIRUET SORTIROVKU SLIYANIEM, KOGDA "SVECHKA SZHIGAETSYA S 
OBOIH KONCOV", PODOBNO TEM PROCEDURAM PROSMOTRA |LEMENTOV FAJLA, KOTORYE 
PRIMENYALISX PRI BYSTROJ SORTIROVKE, PORAZRYADNOJ OBMENNOJ SORTIROVKE I~T.~D.
 mY ANALIZIRUEM ISHODNYJ FAJL SLEVA I SPRAVA, DVIGAYASX K SEREDINE. 
pROPUSTIM POKA PERVUYU STROKU I RASSMOTRIM PEREHOD OT VTOROJ STROKI K 
TRETXEJ. sLEVA MY VIDIM VOZRASTAYUSHCHIJ OTREZOK $503$ $703$ $765$, A SPRAVA, 
ESLI CHITATX SPRAVA NALEVO, IMEEM OTREZOK $087$ $512$ $677$. sLIYANIE |TIH 
DVUH POSLEDOVATELXNOSTEJ DAET PODFAJL $087$ $503$ $512$ $677$ $703$ $765$, 
KOTORYJ POMESHCHAETSYA SLEVA V STROKE~3. zATEM KLYUCHI $061$ $612$ $908$ V 
STROKE~2 SLIVAYUTSYA S~$170$ $509$ $897$, I REZULXTAT $(061$ $170$ $509$ 
$612$ $897$ $908)$ ZAPISYVAETSYA \emph{SPRAVA} V STROKE~3. nAKONEC, $154$ 
$275$ $426$ $653$ SLIVAETSYA S $653$ (PEREKRYTIE OBNARUZHIVAETSYA PREZHDE, 
CHEM ONO MOZHET PRIVESTI K VREDNYM POSLEDSTVIYAM), I REZULXTAT ZAPISYVAETSYA 
SLEVA. tOCHNO TAK ZHE STROKA~2 POLUCHILASX IZ ISHODNOGO FAJLA V STROKE~1.
 
vERTIKALXNYMI LINIYAMI V TABL.~1 OTMECHENY GRANICY MEZHDU OTREZKAMI. eTO TAK 
NAZYVAEMYE "STUPENXKI VNIZ", GDE MENXSHIJ |LEMENT SLEDUET ZA BOLXSHIM. v 
SEREDINE FAJLA OBYCHNO VOZNIKAET DVUSMYSLENNAYA SITUACIYA, KOGDA PRI DVIZHENII 
S OBOIH KONCOV MY PROCHITYVAEM ODIN I TOT ZHE KLYUCH; |TO NE PRIVEDET K 
OSLOZHNENIYAM, ESLI PROYAVITX CHUTOCHKU OSTOROZHNOSTI, KAK V 
SLEDUYUSHCHEM ALGORITME. tAKOJ METOD PO TRADICII NAZYVAETSYA 
"ESTESTVENNYM" SLIYANIEM, POTOMU CHTO ON ISPOLXZUET OTREZKI, KOTORYE 
"ESTESTVENNO" OBRAZUYUTSYA V ISHODNOM FAJLE.

\alg N.(sORTIROVKA ESTESTVENNYM DVUHPUTEVYM SLIYANIEM.) pRI SORTIROVKE 
ZAPISEJ $R_1$, \dots, $R_N$ ISPOLXZUYUTSYA DVE OBLASTI PAMYATI, KAZHDAYA IZ 
KOTORYH MOZHET SODERZHATX $N$~ZAPISEJ. dLYA UDOBSTVA OBOZNACHIM ZAPISI, 
NAHODYASHCHIESYA VO VTOROJ OBLASTI,
%%196
CHEREZ $R_{N+1}$, \dots, $R_{2N}$, HOTYA V DEJSTVITELXNOSTI ZAPISX~$R_{N+1}$ 
MOZHET I NE PRIMYKATX NEPOSREDSTVENNO K~$R_N$. nACHALXNOE SODERZHIMOE ZAPISEJ 
$R_{N+1}$, \dots, $R_{2N}$ NE IMEET ZNACHENIYA. pOSLE ZAVERSHENIYA SORTIROVKI 
KLYUCHI BUDUT UPORYADOCHENY: $K_1\le\ldots\le K_N$.
\picture{rIS. 30.  sORTIROVKA SLIYANIEM.}

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $s\asg0$. (pRI $s=0$ MY BUDEM 
PERESYLATX ZAPISI IZ OBLASTI $(R_1, \ldots, R_N)$ V OBLASTX $(R_{N+1}, 
\ldots, R_{2N})$; PRI $s=1$ OBLASTI PO OTNOSHENIYU K PERESYLKAM POMENYAYUTSYA ROLYAMI.)

\st[pODGOTOVKA K PROSMOTRU.] eSLI $s=0$, TO USTANOVITX $i\asg1$, 
$j\asg N$, $k\asg N+1$, $l\asg2N$; ESLI $s=1$, TO USTANOVITX $i\asg N+1$, 
$j\asg2N$, $k\asg1$, $l\asg N$. (pEREMENNYE $i$, $j$, $k$, $l$ UKAZYVAYUT 
TEKUSHCHIE POZICII VO VHODNYH "FAJLAH", OTKUDA IDET CHTENIE, I V VYHODNYH 
"FAJLAH", KUDA IDET ZAPISX.) uSTANOVITX $d\asg 1$, $f\asg1$. 
(pEREMENNAYA~$d$ OPREDELYAET TEKUSHCHEE NAPRAVLENIE VYVODA, $f$ 
USTANAVLIVAETSYA RAVNOJ~0, ESLI NEOBHODIMY DALXNEJSHIE PROSMOTRY.)

\st[sRAVNENIE $K_i:K_j$] eSLI $K_i>K_j$, PEREJTI K SHAGU~\stp{8}. eSLI 
$i=j$, USTANOVITX $P_k\asg R_i$ I PEREJTI K SHAGU \stp{13}.

\st[pERESYLKA $R_i$.] (shAGI \stp{4}--\stp{7} ANALOGICHNY SHAGAM 
M3--M4 ALGORITMA~M.) uSTANOVITX $R_k\asg R_i$, $k\asg k+d$.

\st[sTUPENXKA VNIZ?] uVELICHITX $i$ NA~1. zATEM, ESLI $K_{i-1}\le K_i$, 
VOZVRATITXSYA K SHAGU \stp{3}.
\st [pERESYLKA $R_j$.] uSTANOVITX $R_k\asg R_j$, 
$k\asg k+d$.
\st[sTUPENXKA VNIZ?] uMENXSHITX $j$ NA~1. zATEM, ESLI $K_{j+1}\le K_j$, 
VOZVRATITXSYA K SHAGU \stp{6}; V PROTIVNOM SLUCHAE PEREJTI K SHAGU \stp{12}.

%% 197
\st[pERESYLKA $R_j$.] (shAGI \stp{8}--\stp{11} DVOJSTVENNY PO OTNOSHENIYU K 
SHAGAM~\stp{4}--\stp{7}.) uSTANOVITX $R_k\asg R_j$, $k\asg k+d$.

\st[sTUPENXKA VNIZ?] uMENXSHITX $j$ NA 1. zATEM, ESLI 
$K_{j+1}\le K_j$, VOZVRATITXSYA K SHAGU \stp{3}.

\st[pERESYLKA $R_i$.] uSTANOVITX~$R_k\asg R_i$, $k\asg k+d$.

\st[sTUPENXKA VNIZ?] uVELICHITX $i$ NA~$1$. zATEM, ESLI 
$K_{i-1}\le K_i$, VOZVRATITXSYA K SHAGU \stp{10}.

\st[pEREKLYUCHENIE NAPRAVLENIYA.] uSTANOVITX $f\asg0$, $d\asg-d$ I 
VZAIMOZAMENITX $k\xchg l$. vOZVRATITXSYA K SHAGU \stp{3}.

\st[pEREKLYUCHENIE OBLASTEJ.] eSLI $f=0$, TO USTANOVITX $s\asg 1-s$ I 
VOZVRATITXSYA K~\stp{2}. v PROTIVNOM SLUCHAE SORTIROVKA ZAVERSHENA; ESLI 
$s=0$, TO USTANOVITX 
$(R_1,~\ldots, R_N)\asg(R_{N+1}, \ldots, R_{2N})$. (eSLI REZULXTAT MOZHNO 
OSTAVITX V OBLASTI~$(R_{N+1}, \ldots, R_{2N})$,  TO POSLEDNEE KOPIROVANIE NEOBYAZATELXNO.)
\algend

v |TOM ALGORITME ESTX ODNA NEBOLXSHAYA TONKOSTX, KOTORAYA OB�YASNYAETSYA V UPR.~5.

zAPROGRAMMIROVATX ALGORITM~N DLYA MASHINY~\MIX\ NETRUDNO, NO OSNOVNYE 
SVEDENIYA O EGO POVEDENII MOZHNO POLUCHITX I BEZ POSTROENIYA VSEJ PROGRAMMY. 
eSLI FAJL SLUCHAEV, TO V NEM OKOLO
${1\over2}N$ VOZRASTAYUSHCHIH OTREZKOV, TAK KAK $K_i>K_{i+1}$ S 
VEROYATNOSTXYU~$1\over2$; PODROBNAYA INFORMACIYA O CHISLE OTREZKOV PRI 
NESKOLXKO OTLICHNYH PREDPOLOZHENIYAH BYLA POLUCHENA V P.~5.1.3. pRI KAZHDOM 
PROSMOTRE CHISLO OTREZKOV SOKRASHCHAETSYA VDVOE (ZA ISKLYUCHENIEM NEOBYCHNYH 
SLUCHAEV, TAKIH, KAK SITUACIYA, OPISANNAYA V UPR.~6). tAKIM OBRAZOM, CHISLO 
PROSMOTROV, KAK PRAVILO, SOSTAVLYAET OKOLO~$\log_2 N$. pRI KAZHDOM PROSMOTRE 
MY DOLZHNY PEREPISATX VSE $N$~ZAPISEJ, I, KAK POKAZANO V UPR.~2, B\'OLXSHAYA 
CHASTX VREMENI ZATRACHIVAETSYA V SHAGAH~N3, N4, N5, N8, 
N9. eSLI SCHITATX, CHTO RAVNYE KLYUCHI VSTRECHAYUTSYA S MALOJ VEROYATNOSTXYU, 
TO VREMYA, ZATRACHIVAEMOE VO VNUTRENNEM CIKLE, MOZHNO 
OHARAKTERIZOVATX SLEDUYUSHCHIM OBRAZOM:
\ctable{
\hfill# & # & #\cr
\hbox{shAG}\hfill&\hfill\hbox{oPERACII}\hfill&\hfill\hbox{vREMYA}\hfill\cr
$\matrix{N3\cr}$ & $\matrix{|CMPA|, |JG|, |JE|\cr}$ & $\matrix{3.5u}$ \cr
$\hbox{lIBO}\left\{
\matrix{
N4\cr
N5\cr
}\right.$
& 
$
\matrix{
|STA|, |INC| \hfill\cr
|INC|, |LDA|, |CMPA|, |JGE|\hfill \cr
}
$
&
$\matrix{
\phantom{0.}3u\cr
\phantom{0.}6u\cr
}$
\cr 
$\hbox{lIBO}\left\{
\matrix{
N8 \cr
N9 \cr
}\right.$
&
$\matrix{
|STX|, |INC|\hfill \cr
|DEC|, |LDX|, |CMPX|, |JGE|\hfill\cr
}$
&
$\matrix{
\phantom{0.}3u\cr
\phantom{0.}6u\cr
}$
\cr
}
tAKIM OBRAZOM, PRI KAZHDOM PROSMOTRE NA KAZHDUYU ZAPISX ZATRACHIVAETSYA 
$12.5$~EDINIC VREMENI, I OBSHCHEE VREMYA RABOTY ASIMPTOTICHESKI PRIBLIZHAETSYA 
K~$12.5N\log_2 N$ KAK V SREDNEM, TAK I V NAIHUDSHEM SLUCHAE. eTO MEDLENNEE 
BYSTROJ SORTIROVKI I NE NASTOLXKO LUCHSHE VREMENI RABOTY PIRAMIDALXNOJ 
SORTIROVKI, CHTOBY OPRAVDATX VDVOE BOLXSHIJ RASHOD PAMYATI, TAK KAK 
ASIMPTOTICHESKOE VREMYA RABOTY PROGRAMMY~5.2.3H RAVNO $16N\log_2 N$.

%% 198

v ALGORITME~N GRANICY MEZHDU OTREZKAMI POLNOSTXYU OPREDELYAYUTSYA 
"STUPENXKAMI VNIZ". tAKOJ PODHOD OBLADAET TEM VOZMOZHNYM PREIMUSHCHESTVOM, 
CHTO ISHODNYE FAJLY S PREOBLADANIEM VOZRASTAYUSHCHEGO \emph{ILI UBYVAYUSHCHEGO} 
RASPOLOZHENIYA |LEMENTOV MOGUT OBRABATYVATXSYA OCHENX BYSTRO, NO PRI |TOM 
ZAMEDLYAETSYA OSNOVNOJ CIKL VYCHISLENIJ. vMESTO PROVEROK STUPENEK VNIZ MOZHNO 
PRINUDITELXNO USTANOVITX DLINU OTREZKOV, SCHITAYA, CHTO VSE 
OTREZKI ISHODNOGO FAJLA IMEYUT DLINU~$1$, POSLE PERVOGO PROSMOTRA 
VSE OTREZKI (KROME, VOZMOZHNO, POSLEDNEGO) IMEYUT DLINU 2, \dots, 
POSLE $k\hbox{-Go}$ PROSMOTRA VSE OTREZKI (KROME, VOZMOZHNO, 
POSLEDNEGO) IMEYUT DLINU~$2^k$. v OTLICHIE OT "ESTESTVENNOGO" SLIYANIYA V 
ALGORITME~N TAKOJ SPOSOB NAZYVAETSYA \emph{PROSTYM} DVUHPUTEVYM SLIYANIEM.

aLGORITM PROSTOGO DVUHPUTEVOGO SLIYANIYA OCHENX NAPOMINAET ALGORITM~N---ON 
OPISYVAETSYA, PO SUSHCHESTVU, TOJ ZHE BLOK-SHEMOJ;
TEM NE MENEE METODY DOSTATOCHNO OTLICHAYUTSYA DRUG OT DRUGA, I PO|TOMU STOIT 
ZAPISATX VESX ALGORITM CELIKOM.

\alg S.(sORTIROVKA PROSTYM DVUHPUTEVYM SLIYANIEM.) kAK I V ALGORITME~N, PRI 
SORTIROVKE ZAPISEJ $R_1$, \dots, $R_N$ ISPOLXZUYUTSYA DVE OBLASTI PAMYATI.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $s\asg0$, $p\asg1$. 
(sMYSL PEREMENNYH~$s$, $i$, $j$, $k$, $l$, $d$ SM. V ALGORITME~N. zDESX 
$p$---RAZMER VOZRASTAYUSHCHIH OTREZKOV, KOTORYE BUDUT SLIVATXSYA VO VREMYA 
TEKUSHCHEGO PROSMOTRA; $q$ I~$r$---KOLICHESTVA NESLITYH |LEMENTOV V OTREZKAH.)

\st[pODGOTOVKA K PROSMOTRU.] eSLI $s=0$, TO USTANOVITX $i\asg1$, 
$j\asg N$, $k\asg N$, $l\asg2N+1$; ESLI $s=1$, TO USTANOVITX $i\asg N+1$, 
$j\asg2N$, $k\asg0$, $l\asg N+1$. zATEM USTANOVITX $d\asg1$, $q\asg p$, 
$r\asg p$.

\st[sRAVNENIE $K_i:K_j$.] eSLI $K_i>K_j$, TO PEREJTI K SHAGU~\stp{8}.

\st[pERESYLKA $R_i$] uSTANOVITX $k\asg k+d$, $R_k\asg R_i$.

\st[kONEC OTREZKA?] uSTANOVITX $i\asg i+1$, $q\asg q-1$. eSLI $q > 0$, TO 
VOZVRATITXSYA K SHAGU~\stp{3}.

\st[pERESYLKA $R_j$.] uSTANOVITX $k\asg k+d$. zATEM, ESLI $k=l$, PEREJTI K 
SHAGU~\stp{13}; V PROTIVNOM SLUCHAE USTANOVITX
$R_k\asg R_j$.

\st[kONEC OTREZKA?] uSTANOVITX $j\asg j-1$, $r\asg r-1$. 
eSLI~$r>0$, VOZVRATITXSYA K SHAGU \stp{6}; V PROTIVNOM SLUCHAE PEREJTI
K SHAGU \stp{12}.

\st [pERESYLKA $R_j$.] uSTANOVITX $k\asg k+d$, $R_k\asg R_j$ 

\st[kONEC OTREZKA?] uSTANOVITX $j\asg j-1$, $r\asg r-1$. 
eSLI~$r> 0$, TO VOZVRATITXSYA K SHAGU~\stp{3}. 
\st[pERESYLKA $R_i$.] uSTANOVITX $k\asg k+d$. zATEM, ESLI $k=l$,
PEREJTI K SHAGU~\stp{13}; V PROTIVNOM SLUCHAE USTANOVITX
$R_k\asg R_i$.
%% 199
\st[kONEC OTREZKA?] uSTANOVITX $i\asg i+1$, $q\asg q-1$. eSLI $q > 0$, TO 
VOZVRATITXSYA K SHAGU \stp{10}.

\st[pEREKLYUCHENIE NAPRAVLENIYA.] uSTANOVITX $q\asg p$, $r\asg p$, $d\asg -d$ 
I VZAIMOZAMENITX $k\xchg l$. vOZVRATITXSYA K SHAGU \stp{3}.

\st[pEREKLYUCHENIE OBLASTEJ.] uSTANOVITX $p\asg p+p$. eSLI $p<N$, TO 
USTANOVITX $s\asg 1-s$ I VOZVRATITXSYA K~\stp{2}. v PROTIVNOM SLUCHAE 
SORTIROVKA ZAVERSHENA; ESLI $s=0$, TO USTANOVITX
$$
(R_1, \ldots, R_n)\asg (R_{N+1}, \ldots, R_{2N}).
$$
(nEZAVISIMO OT RASPREDELENIYA ISHODNOGO FAJLA POSLEDNEE KOPIROVANIE BUDET 
VYPOLNENO TOGDA I TOLXKO TOGDA, KOGDA ZNACHENIE~$\ceil{\log_2 N}$ NECHETNO. 
tAK CHTO MOZHNO ZARANEE PREDSKAZATX POLOZHENIE OTSORTIROVANNOGO FAJLA, I 
KOPIROVANIE, KAK PRAVILO, NE TREBUETSYA.)
\algend

{\def|{\mskip\thinmuskip\vert\hidewidth}
 \catcode`\!=\active
 \def!{\mskip\thinmuskip\vrule width 0.5mm\hidewidth}
\htable{tABLICA 2}%
{sORTIROVKA PROSTYM DVUHPUTEVYM SLIYANIEM}
{\bskip$#$\bskip&&\bskip$#$\bskip\cr
503|& 087|& 512|& 061|& 908|& 170|& 897|& 275!& 653|& 426|& 154|& 509|& 612|& 677|& 765|& 703\cr
503 & 703|& 512 & 677|& 509 & 908|& 426 & 897!& 653 & 275 & 170 & 154|& 612 & 061|& 765 & 087\cr
087 & 503 & 703 & 765|& 154 & 170 & 509 & 908!& 897 & 653 & 426 & 275|& 677 & 612 & 512 & 061\cr
061 & 087 & 503 & 512 & 612 & 677 & 703 & 765!& 908 & 897 & 653 & 509 & 426 & 275 & 170 & 154\cr
061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908\cr
}
}

pRIMER RABOTY ALGORITMA SM. V TABL.~2. dOVOLXNO UDIVITELXNO, CHTO |TOT 
METOD SPRAVEDLIV I TOGDA, KOGDA $N$ NE YAVLYAETSYA STEPENXYU~2; SLIVAEMYE 
OTREZKI NE VSE IMEYUT DLINU $2^k$, TEM NE MENEE NIKAKIH YAVNYH MER 
PREDOSTOROZHNOSTI NA SLUCHAJ TAKIH ISKLYUCHENIJ NE PREDUSMOTRENO! (sM. 
UPR.~8.) pROVERKI STUPENEK VNIZ ZAMENENY UMENXSHENIEM PEREMENNYH~$q$ I~$r$ 
I PROVERKOJ NA RAVENSTVO NULYU. bLAGODARYA |TOMU VREMYA RABOTY NA MASHINE 
\MIX\ ASIMPTOTICHESKI PRIBLIZHAETSYA K $11N\log_2 N$~EDINICAM, CHTO NESKOLXKO 
LUCHSHE ZNACHENIYA, KOTOROGO NAM UDALOSX DOBITXSYA V ALGORITME~N.

nA PRAKTIKE IMEET SMYSL KOMBINIROVATX ALGORITM~S S PROSTYMI VSTAVKAMI; 
VMESTO PERVYH CHETYREH PROSMOTROV ALGORITMA~S MOZHNO PROSTYMI VSTAVKAMI 
OTSORTIROVATX GRUPPY, SKAZHEM, IZ 16~|LEMENTOV, ISKLYUCHIV TAKIM OBRAZOM 
DOVOLXNO RASTOCHITELXNYE VSPOMOGATELXNYE OPERACII, SVYAZANNYE SO SLIYANIEM 
KOROTKIH FAJLOV. kAK MY UZHE VIDELI V SLUCHAE BYSTROJ SORTIROVKI, 
TAKOE KOMBINIROVANIE METODOV NE VLIYAET/NA ASIMPTOTICHESKOE VREMYA RABOTY, NO 
DAET TEM NE MENEE, NEMALUYU VYGODU.

rASSMOTRIM TEPERX ALGORITMY~N I~S S TOCHKI ZRENIYA STRUKTUR DANNYH. pOCHEMU 
NAM NEOBHODIMA PAMYATX POD $2N$, A NE POD $N$
%% 200
~ZAPISEJ? pRICHINA OTNOSITELXNO PROSTA: MY RABOTAEM S CHETYRXMYA SPISKAMI 
PEREMENNOGO RAZMERA (DVA "VHODNYH SPISKA" I DVA "VYHODNYH SPISKA" V KAZHDOM 
PROSMOTRE); PRI |TOM DLYA KAZHDOJ PARY POSLEDOVATELXNO RASPREDELENNYH 
SPISKOV MY POLXZUEMSYA STANDARTNYM PONYATIEM "VSTRECHNOGO ROSTA", 
OBSUZHDAVSHIMSYA V (P.~2.2.2. nO V LYUBOJ MOMENT VREMENI POLOVINA PAMYATI NE 
ISPOLXZUETSYA, I POSLE NEKOTOROGO RAZMYSHLENIYA STANOVITSYA YASNO, CHTO V 
DEJSTVITELXNOSTI, DLYA NASHIH CHETYREH SPISKOV SLEDOVALO BY VOSPOLXZOVATXSYA 
\emph{SVYAZANNYM} RASPREDELENIEM PAMYATI. eSLI K KAZHDOJ IZ $N$~ZAPISEJ 
DOBAVITX POLE SVYAZI, TO VSE NEOBHODIMOE MOZHNO PRODELATX, POLXZUYASX 
ALGORITMAMI SLIYANIYA, KOTORYE PROIZVODYAT PROSTYE MANIPULYACII SO SVYAZYAMI I 
SOVSEM NE PEREMESHCHAYUT SAMI ZAPISI. dOBAVLENIE $N$~POLEJ SVYAZI, KAK 
PRAVILO, VYGODNEE, CHEM DOBAVLENIE PROSTRANSTVA PAMYATI ESHCHE POD 
$N$~ZAPISEJ, A OTKAZAVSHISX OT PEREMESHCHENIYA ZAPISEJ, MY MOZHEM 
TAKZHE S|KONOMITX I VREMYA. iTAK, NAM NUZHNO RASSMOTRETX ALGORITM, PODOBNYJ 
SLEDUYUSHCHEMU.

\alg L.(sORTIROVKA POSREDSTVOM SLIYANIYA SPISKOV.) pREDPOLAGAETSYA, CHTO 
ZAPISI $R_1$, \dots, $R_N$ SODERZHAT KLYUCHI $K_1$,~\dots, $K_N$ I "POLYA 
SVYAZI" $L_1$,~\dots, $L_N$, V KOTORYH MOGUT HRANITXSYA CHISLA OT~$-(N+1)$ 
DO~$(N+1)$. v NACHALE I V KONCE FAJLA IMEYUTSYA ISKUSSTVENNYE ZAPISI~$R_0$ 
I~$R_{N+1}$ S POLYAMI SVYAZI~$L_0$ I~$L_{N+1}$ eTOT ALGORITM SORTIROVKI 
SPISKOV USTANAVLIVAET POLYA SVYAZI TAKIM OBRAZOM, CHTO ZAPISI OKAZYVAYUTSYA 
SVYAZANNYMI V VOZRASTAYUSHCHEM PORYADKE. pOSLE ZAVERSHENIYA SORTIROVKI $L_0$ 
UKAZYVAET NA ZAPISX S NAIMENXSHIM KLYUCHOM; PRI $1\le k \le N$ SVYAZX~$L_k$ 
UKAZYVAET NA ZAPISX, SLEDUYUSHCHUYU ZA~$R_k$, A ESLI $R_k$---ZAPISX S 
NAIBOLXSHIM KLYUCHOM, TO $L_k=0$. (sM. FORMULY (5.2.1--9).)

v PROCESSE VYPOLNENIYA |TOGO ALGORITMA ZAPISI~$R_0$ I~$R_{N+1}$ SLUZHAT 
"GOLOVAMI" DVUH LINEJNYH SPISKOV, PODSPISKI KOTORYH V DANNYJ MOMENT 
SLIVAYUTSYA. oTRICATELXNAYA SVYAZX OZNACHAET KONEC PODSPISKA, O KOTOROM 
IZVESTNO, CHTO ON UPORYADOCHEN; NULEVAYA SVYAZX OZNACHAET KONEC VSEGO SPISKA. 
pREDPOLAGAETSYA, CHTO $N\ge 2$.

chEREZ "$\abs{L_s}\asg p$" OBOZNACHENA OPERACIYA "PRISVOITX $L_s$ 
ZNACHENIE~$p$ ILI~$-p$, SOHRANIV PREZHNIJ ZNAK $L_s$". tAKAYA 
OPERACIYA LEGKO REALIZUETSYA NA MASHINE \MIX, NO, K SOZHALENIYU, |TO NE TAK DLYA 
BOLXSHINSTVA evm. nETRUDNO IZMENITX ALGORITM, CHTOBY POLUCHITX STOLX ZHE 
|FFEKTIVNYJ METOD I DLYA BOLXSHINSTVA DRUGIH MASHIN.

\st[pODGOTOVITX DVA SPISKA.] uSTANOVITX $L_0\asg1$, $L_{N+1}\asg2$,
 $L_i\asg -(i+2)$ PRI~$l\le i\le N-2$ I~$L_{N-1}\asg L_N\asg0$. (mY 
SOZDALI DVA SPISKA, SODERZHASHCHIE SOOTVETSTVENNO ZAPISI~$R_1$, $R_3$, $R_5$,
~\dots{} I~$R_2$, $R_4$, $R_6$,~\dots{}; OTRICATELXNYE SVYAZI GOVORYAT O TOM,
 CHTO KAZHDYJ UPORYADOCHENNYJ "PODSPISOK" SOSTOIT VSEGO LISHX IZ ODNOGO 
|LEMENTA. dRUGOJ SPOSOB VYPOLNITX |TOT SHAG,
%% 201



\bye