\input style
\chapnotrue
\chapno=5\subchno=2\subsubchno=3
%% 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
IZVLEKAYA POLXZU IZ UPORYADOCHENNOSTI, KOTORAYA MOGLA PRISUTSTVOVATX V 
ISHODNYH DANNYH, SM. V UPR.~12.)

\st[nACHATX NOVYJ PROSMOTR.] uSTANOVITX $s\asg 0$, $t\asg N+1$, $p\asg L_s$,
 $q\asg L_t$. eSLI $q=0$, TO RABOTA ALGORITMA ZAVERSHENA. (pRI KAZHDOM 
PROSMOTRE $p$ I~$q$ PROBEGAYUT PO SPISKAM, KOTORYE PODVERGAYUTSYA SLIYANIYU; 
$s$ OBYCHNO UKAZYVAET NA POSLEDNYUYU OBRABOTANNUYU ZAPISX TEKUSHCHEGO PODSPISKA,
 a $t$---NA KONEC TOLXKO CHTO VYVEDENNOGO PODSPISKA.)

\st[sRAVNITX $K_p:K_q$.] eSLI $K_p>K_q$, TO PEREJTI K~\stp{6}.

\st[pRODVINUTX $p$.] uSTANOVITX $\abs{L_s}\asg p$, $s\asg p$, $p\asg L_p$. 
eSLI $p>0$, TO VOZVRATITXSYA K~\stp{3}.

\st[zAKONCHITX PODSPISOK.] uSTANOVITX $L_s\asg q$, $s\asg t$. 
zATEM USTANOVITX $t\asg q$ I~$q\asg L_q$ ODIN ILI BOLEE RAZ, POKA 
NE STANET $q\le 0$, POSLE CHEGO PEREJTI K~\stp{8}.

\st[pRODVINUTX $q$.] (shAGI \stp{6} I~\stp{7} DVOJSTVENNY PO 
OTNOSHENIYU K~\stp{4} I~\stp{5}.) uSTANOVITX $\abs{L_s}\asg q$, $s\asg q$, 
$q\asg L_q$. eSLI~$q>0$, TO VOZVRATITXSYA K~\stp{3}.

\st[zAKONCHITX PODSPISOK.] uSTANOVITX $L_s\asg p$, $s\asg t$. 
zATEM USTANOVITX $t\asg p$ I~$p\asg L_p$ ODIN ILI BOLEE RAZ, POKA NE STANET~$p>0$.

\st[kONEC PROSMOTRA?] (k |TOMU MOMENTU $p\le 0$ I~$q\le 0$, TAK KAK OBA 
UKAZATELYA PRODVINULISX DO KONCA SOOTVETSTVUYUSHCHIH PODSPISKOV.) 
uSTANOVITX~$p\asg -p$,  $q\asg -q$. eSLI $q=0$, 
TO USTANOVITX~$\abs{L_s}\asg p$, $\abs{L_t}\asg 0$, I VOZVRATITXSYA 
K~\stp{2}; V PROTIVNOM SLUCHAE VOZVRATITXSYA K~\stp{3}.
\algend

pRIMER RABOTY |TOGO ALGORITMA PRIVEDEN V TABL.~3, V KOTOROJ POKAZANY 
SVYAZI K MOMENTU VYPOLNENIYA SHAGA~L2. pO OKONCHANII RABOTY ALGORITMA MOZHNO, 
POLXZUYASX METODOM IZ UPR.~5.2--12, PERERAZMESTITX ZAPISI TAK, CHTOBY IH 
KLYUCHI BYLI UPORYADOCHENY. mOZHNO ZAMETITX INTERESNUYU ANALOGIYU MEZHDU SLIYANIEM 
SPISKOV I SLOZHENIEM RAZREZHENNYH MNOGOCHLENOV (SM. ALGORITM 2.2.4a).
{\catcode`\!=\active\def!#1.{\omit\hfill$#1$\hfill}
\htable{tABLICA 3}%
{sORTIROVKA POSREDSTVOM SLIYANIYA SPISKOV}%
{\bskip$#$\bskip&&\hfill$#$\bskip\cr
j   &!0.& !1.& !2.& !3.& !4.& !5.& !6.& !7.& !8.& !9.&!10.&!11.&!12.&!13.&!14.&!15.&!16.&!17.\cr
K_i & - & 503& 087& 512& 061& 908& 170& 897& 275& 653& 426& 154& 509& 612& 677& 765& 703&  -\cr
L_j & 1 &  -3&  -4&  -5&  -6&  -7&  -8&  -9& -10& -11& -12& -13& -14& -15& -16&   0&   0&  2\cr
L_j & 2 &  -6&   1&  -8&   3& -10&   5& -11&   7& -13&   9&  12& -16&  14&   0&   0&  15&  4\cr
L_j & 4 &   3&   1& -11&   2& -13&   8&   5&   7&   0&  12&  10&   9&  14&  16&   0&  15&  6\cr
L_j & 4 &   3&   6&   7&   2&   0&   8&   5&   1&  14&  12&  10&  13&   9&  16&   0&  15& 11\cr
L_j & 4 &  12&  11&  13&   2&   0&   8&   5&  10&  14&   1&   6&   3&   9&  16&   7&  15&  0\cr
}
}

nAPISHEM TEPERX \MIX-PROGRAMMU DLYA ALGORITMA~L, CHTOBY VYYASNITX, STOLX LI 
VYGODNO OPERIROVATX SPISKAMI S TOCHKI ZRENIYA VREMENI, KAK I S TOCHKI ZRENIYA PROSTRANSTVA?
%%202
\prog L.(sORTIROVKA POSREDSTVOM SLIYANIYA SPISKOV.) dLYA UDOBSTVA 
PREDPOLAGAETSYA, CHTO ZAPISI ZANIMAYUT ODNO SLOVO, PRICHEM $L_j$ HRANITSYA V 
POLE $(0:2)$, A $K_j$---V POLE $(3:5)$ YACHEJKI $|INPUT|+j$;
ZNACHENIYA REGISTROV: $|rI1|\equiv p$, $|rI2|\equiv q$, $|rI3|\equiv s$, 
$|rI4|\equiv t$ $|rA|\equiv R_q$; $N\ge 2$.
\code
L    & EQU  & 0:2          &       & oPREDELENIE IMEN POLEJ.
ABSL & EQU  & 1:2
KEY  & EQU  & 3:5
START& ENT1 & N-2          & 1     & L1. pODGOTOVITX DVA SPISKA.
     & ENNA & 2,1          & N-2
     & STA  & INPUT,1(L)   & N-2   & $L_i\asg -(i+2)$.
     & DEC1 & 1            & N-2
     & J1P  & *-3          & N-2   & $N-2\ge i>0$.
     & ENTA & 1            & 1
     & STA  & INPUT(L)     & 1     & $L_0\asg 1$.
     & ENTA & 2            & 1
     & STA  & INPUT+N+1(L) & 1     & $L_{N+1}\asg2$.
     & STZ  & INPUT+ N-1(L)& 1     & $L_{N-1}\asg 0$.
     & STZ  & INPUT +N(L)  & 1     & $L_N\asg 0$.
     & JMP  & L2           & 1     & k L2.
L3Q  & LDA  & INPUT,2      & C''+B'& L3. sRAVNITX $K_p:K_q$.
L3P  & CMPA & INPUT,1(KEY) & C
     & JL   & L6           & C     & k L6, ESLI $K_q<K_p$.
L4   & ST1  & INPUT,3(ABSL)& C'    & L4. pRODVINUTX~$p$. $\abs{L_s}\asg p$.
     & ENT3 & 0,1          & C'    & $s-p$.
     & LD1  & INPUT, 1(L)  & C'    & $p\asg L_p$
     & J1P  & L3P          & C'    & k L3, ESLI~$p>0$.
L5   & ST2  & INPUT,3(L)   & B'    & L5. zAKONCHITX PODSPISOK. $L_s\asg q$.
     & ENT3 & 0,4          & B'    & $s\asg t$.
     & ENT4 & 0,2          & D'    & $t\asg q$.
     & LD2  & INPUT,2(L)   & D'    & $q\asg L_q$.
     & J2P  & *-2          & D'    & pOVTORITX, ESLI $q>0$.
     & JMP  & L8           & B'    & k L8
L6   & ST2  & INPUT,3(ABSL)& C''   & L6. pRODVINUTX~$q$. $\abs{L_s}\asg q$.
     & ENT3 & 0,2          & C''   & $s\asg q$.
     & LD2  & INPUT,2(L)   & C''   & $q\asg L_q$.
     & J2P  & L3Q          & C''   & k L3, ESLI~$q>0$.
L7   & ST1  & INPUT,3(L)   & B''   & L7. zAKONCHITX PODSPISOK. $L_s\asg p$.
     & ENT3 & 0,4          & B''   & $s\asg t$.
     & ENT4 & 0,1          & D''   & $t\asg p$.
     & LD1  & INPUT, 1(L)  & D''   & $p\asg L_p$.
     & J1P  & *-2          & D''   & pOVTORITX, ESLI~$p>0$.
L8   & ENN1 & 0,1          & B     & L8. kONEC PROSMOTRA? $p\asg -p$.
     & ENN2 & 0,2          & B     & $q\asg -q$.
     & J2NZ & L3Q          & B     & k L3, ESLI $q\ne0$.
     & ST1  & INPUT,3(ABSL)& A     & $\abs{L_s}\asg p$.
     & STZ  & INPUT,4(ABSL)& A     & $\abs{L_t}\asg0$.
%%203
L2   & ENT3 & 0            & A+1   & L2. nACHATX NOVYJ PROSMOTR, $s\asg0$.
     & ENT4 & N+1          & A+1   & $t\asg N+1$.
     & LD1  & INPUT (L)    & A+1   & $p\asg L_s$.
     & LD2  & INPUT+N+1(L) & A+1   & $q\asg L_t$.
     & J2NZ & L3Q          & A+1   & k L3, ESLI $q \ne 0$.
\endcode

vREMYA RABOTY |TOJ PROGRAMMY MOZHNO OCENITX PRI POMOSHCHI METODOV, KOTORYMI MY 
UZHE NE RAZ POLXZOVALISX (SM. UPR.~13, 14);
V SREDNEM ONO RAVNO PRIBLIZITELXNO $(10N \log_2 N+4.92N)$~EDINIC S 
NEBOLXSHIM STANDARTNYM OTKLONENIEM PORYADKA $\sqrt{N}$. v UPR.~15 POKAZANO, 
CHTO ZA SCHET NEKOTOROGO UDLINENIYA PROGRAMMY MOZHNO SOKRATITX VREMYA PRIMERNO 
DO~$9N\log_2N$.

iTAK, V SLUCHAE VNUTRENNEGO SLIYANIYA SVYAZANNOE RASPREDELENIE PAMYATI IMEET 
BESSPORNYE PREIMUSHCHESTVA PERED POSLEDOVATELXNYM RASPREDELENIEM: TREBUETSYA 
MENXSHE PAMYATI, I PROGRAMMA RABOTAET NA 10--20\% BYSTREE. aNALOGICHNYE 
ALGORITMY OPUBLIKOVANY l.~dZH.~vUDRAMOM [{\sl IBM Systems J.\/}, {\bf 8} 
(1969), 189--203] I a.~d.~vUDALLOM [{\sl sOTR. J.\/}, {\bf 13} (1970), 110--111].

\excercises
\ex[20] oBOBSHCHITE ALGORITM~M NA \emph{$k\hbox{-PUTEVOE}$ SLIYANIE} ISHODNYH 
FAJLOV $x_{i1}\le \ldots\le x_{im_i}$ PRI $i=1,$ 2, \dots, $k$.

\ex[m24] sCHITAYA, CHTO VSE $\perm{m+n}{m}$ VOZMOZHNYH RASPOLOZHENIJ 
$m$~|LEMENTOV~$x$ SREDI $n$~|LEMENTOV~$y$ RAVNOVEROYATNY, NAJDITE 
MATEMATICHESKOE OZHIDANIE I STANDARTNOE OTKLONENIE CHISLA VYPOLNENII SHAGA~M2 
V ALGORITME~M. chEMU RAVNY MAKSIMALXNOE I MINIMALXNOE ZNACHENIYA |TOJ VELICHINY?

\rex[20] \exhead(iZMENENIE.) dANY ZAPISI $R_1$,~\dots, $R_M$ I~$R'_1$,
~\dots, $R'_N$, KLYUCHI KOTORYH RAZLICHNY I UPORYADOCHENY, 
T.~E.~$K_1<\ldots<K_M$ I $K'_1<\ldots<K'_N$. 
kAK NUZHNO IZMENITX ALGORITM~M, CHTOBY V 
REZULXTATE SLIYANIYA POLUCHALSYA FAJL, V KOTOROM OTSUTSTVUYUT ZAPISI~$R_i$ 
PERVOGO FAJLA, ESLI VO VTOROM FAJLE TOZHE ESTX ZAPISX S TAKIM ZHE KLYUCHOM?

\ex[21] v TEKSTE OTMECHENO, CHTO SORTIROVKU SLIYANIEM MOZHNO RASSMATRIVATX KAK 
OBOBSHCHENIE SORTIROVKI VSTAVKAMI. pOKAZHITE, CHTO METOD SLIYANIJ 
IMEET NEPOSREDSTVENNOE OTNOSHENIE I K VYBORU IZ DEREVA (VOSPOLXZUJTESX V 
KACHESTVE ILLYUSTRACII RIS.~23).

\rex[21] dOKAZHITE, CHTO V SHAGAH~N6 I~N10 PEREMENNYE~$i$ I~$j$ NE MOGUT 
BYTX RAVNY. (pO|TOMU V |TIH SHAGAH PROVERKA NA SLUCHAJ VOZMOZHNOGO PEREHODA K~N13 NEOBYAZATELXNA.)

\ex[22] nAJDITE TAKUYU PERESTANOVKU $K_1 K_2 \ldots K_{16}$ 
MNOZHESTVA~$\{1, 2, \ldots, 16\}$, CHTO
$$
\displaylines{
  K_2>K_3, K_4>K_5, K_6>K_7, K_8>K_9,\cr
  K_{10}<K_{11}, K_{12}<K_{13}, K_{14}<K_{15},\cr
}
$$
KOTORAYA TEM NE MENEE BUDET OTSORTIROVANA PRI POMOSHCHI ALGORITMA~N VSEGO 
ZA DVA PROSMOTRA. (tAK KAK V ISKOMOJ PERESTANOVKE IMEETSYA NE MENEE 
VOSXMI OTREZKOV, TO MY MOGLI BY OZHIDATX, CHTO POSLE PERVOGO PROSMOTRA 
OSTANUTSYA PO MENXSHEJ MERE CHETYRE OTREZKA, POSLE VTOROGO PROSMOTRA---DVA 
OTREZKA, I SORTIROVKA, KAK PRAVILO, NE ZAVERSHITSYA RANXSHE OKONCHANIYA 
TRETXEGO PROSMOTRA. kAKIM ZHE OBRAZOM MOZHNO OBOJTISX VSEGO DVUMYA PROSMOTRAMI?)

%%204
\ex[16] nAJDITE TOCHNUYU FORMULU, VYRAZHAYUSHCHUYU CHISLO PROSMOTROV ALGORITMA~S 
V VIDE FUNKCII OT~N.

\ex[22] pREDPOLAGAETSYA, CHTO VO VREMYA RABOTY ALGORITMA PEREMENNYE~$q$ 
I~$r$G PREDSTAVLYAYUT DLINY NESLITYH CHASTEJ OTREZKOV, OBRABATYVAEMYH V 
DANNYJ MOMENT; V NACHALE RABOTY -KAK~$q$, TAK I~$r$ USTANAVLIVAYUTSYA 
RAVNYMI~$p$, V TO VREMYA KAK OTREZKI NE VSEGDA IMEYUT TAKUYU DLINU. pOCHEMU ZHE 
ALGORITM TEM NE MENEE RABOTAET PRAVILXNO?

\ex [24] nAPISHITE \MIX-PROGRAMMU DLYA ALGORITMA~S. vYRAZITE 
CHASTOTU VYPOLNENIYA KAZHDOJ KOMANDY CHEREZ VELICHINY, PODOBNYE $A$, $B'$, 
$B''$, $C'$, \dots V PROGRAMME~L.

\ex[25] (d. a. bELL.) pOKAZHITE, CHTO PROSTOE DVUHPUTEVOE SLIYANIE FAJLOV S 
POSLEDOVATELXNO RASPOLOZHENNYMI |LEMENTAMI MOZHNO VYPOLNITX, IMEYA VSEGO 
${3\over2}N$~YACHEEK PAMYATI, A NE $2N$, KAK V ALGORITME~S.

\ex[21] yaVLYAETSYA LI ALGORITM~L ALGORITMOM "USTOJCHIVOJ" SORTIROVKI?

\rex[22] iZMENITE SHAG~L1 ALGORITMA~L TAK, CHTOBY DVUHPUTEVOE SLIYANIE STALO 
"ESTESTVENNYM", IZVLEKAYA POLXZU IZ NALICHIYA VOZRASTAYUSHCHIH OTREZKOV V 
ISHODNOM FAJLE. (v CHASTNOSTI, ESLI ISHODNYE DANNYE UZHE UPORYADOCHENY, 
TO SHAG~L2 ZAVERSHIT RABOTU ALGORITMA SRAZU ZHE POSLE VYPOLNENIYA 
IZMENENNOGO VAMI SHAGA~L1.)

\rex[m34] pROANALIZIRUJTE SREDNEE VREMYA RABOTY PROGRAMMY~L PODOBNO TOMU, 
KAK MY ANALIZIROVALI DRUGIE ALGORITMY V |TOJ GLAVE. dAJTE TOLKOVANIE 
VELICHINAM~$A$, $B$, $B'$, \dots I OB�YASNITE, KAK VYCHISLITX IH TOCHNYE 
SREDNIE ZNACHENIYA. sKOLXKO VREMENI ZATRATIT PROGRAMMA~L NA SORTIROVKU 
16~CHISEL V TABL.~3?

\ex[m24] pUSTX DVOICHNOE PREDSTAVLENIE CHISLA~$N$---|TO 
$2^{e_1}+2^{e_2}+\cdots+2^{e_t}$, GDE $e_1>e_2>\ldots>e_t\ge0$, $t\ge1$. 
dOKAZHITE, CHTO MAKSIMALXNOE CHISLO SRAVNENIJ
KLYUCHEJ, VYPOLNYAEMYH ALGORITMOM~L, RAVNO 
$1-2^{e_t}+\sum{1\le k\le t}(e_k+k-1)2^{e_k}$.

\ex[20] eSLI PROMODELIROVATX VRUCHNUYU RABOTU ALGORITMA~L, TO OBNARUZHITSYA, 
CHTO V NEM INOGDA VYPOLNYAYUTSYA LISHNIE OPERACII; PRIMERNO V POLOVINE 
SLUCHAEV NE NUZHNY PRISVAIVANIYA $\abs{L_s}\asg p$, $\abs{L_s}\asg q$ V 
SHAGAH~L4 I~L6, POSKOLXKU MY IMEEM $L_s=p$ (ILI~$q$) VSYAKIJ RAZ, KOGDA 
VOZVRASHCHAEMSYA IZ SHAGA~L4 (ILI L6) K~L3. kAK ULUCHSHITX PROGRAMMU~L, 
IZBAVIVSHISX OT |TIH  LISHNIH PRISVAIVANII?

\ex[28] rAZRABOTAJTE ALGORITM SLIYANIYA SPISKOV, PODOBNYJ ALGORITMU~L, NO 
OSNOVANNYJ NA TREHPUTEVOM SLIYANII.

\ex[20] (dZH.~mAK-kARTI.) pUSTX DVOICHNOE PREDSTAVLENIE CHISLA~$N$ TAKOE ZHE, 
KAK V UPR.~14, I PREDPOLOZHIM, CHTO DANO $N$~ZAPISEJ, ORGANIZOVANNYH V $t$
UPORYADOCHENNYH PODFAJLOV, IMEYUSHCHIH RAZMERY SOOTVETSTVENNO 
$2^{e_1}$, $2^{e_2}$, \dots, $2^{e_t}$.
pOKAZHITE, KAK MOZHNO SOHRANITX TAKOE SOSTOYANIE PRI DOBAVLENII 
$(N+1)\hbox{-J}$ ZAPISI I~$N\asg N+1$. (pOLUCHENNYJ ALGORITM MOZHNO NAZVATX 
"OPERATIVNOJ" SORTIROVKOJ SLIYANIEM.)

\ex[40] (m.~a.~kRONROD.) mOZHNO LI OTSORTIROVATX FAJL IZ $N$~ZAPISEJ,
 SODERZHASHCHIJ VSEGO DVA OTREZKA:
$$
K_1\le\ldots\le K_M\quad\hbox{I}\quad K_{M+1}\le\ldots\le K_N,
$$
zA $O(N)$ OPERACIJ V PAMYATI S PROIZVOLXNYM DOSTUPOM, \emph{ISPOLXZUYA LISHX 
NEBOLXSHOE DOPOLNITELXNOE PROSTRANSTVO PAMYATI FIKSIROVANNOGO RAZMERA}, NE 
ZAVISYASHCHEGO OT~$M$ I~$N$? (vSE ALGORITMY SLIYANIYA, OPISANNYE V |TOM PUNKTE,
 ISPOLXZUYUT DOPOLNITELXNOE PROSTRANSTVO PAMYATI, PROPORCIONALXNOE~$N$.)

\ex[26] rASSMOTRIM ZHELEZNODOROZHNYJ RAZ�EZD S $n$~"STEKAMI", KAK POKAZANO 
NA RIS.~31 PRI $n=5$; TAKOJ RAZ�EZD IMEET NEKOTOROE OTNOSHENIE K 
ALGORITMAM SORTIROVKI S $n$~PROSMOTRAMI. v UPR.~S~2.2.1--2 PO~2.2.1--5 
MY RASSMOTRELI RAZ�EZDY S ODNIM STEKOM. vY VIDELI, CHTO ESLI S PRAVOGO 
KONCA POSTUPAET $N$~VAGONOV, TO SLEVA MOZHET POYAVITXSYA SRAVNITELXNO 
NEBOLXSHOE KOLICHESTVO IZ $N$~VSEVOZMOZHNYH PERESTANOVOK |TIH VAGONOV.
%% 205

pREDPOLOZHIM, CHTO V RAZ�EZD S $n$~STEKAMI SPRAVA POSTUPAET 
$2^n$~VAGONOV. dOKAZHITE, CHTO PRI POMOSHCHI PODHODYASHCHEJ POSLEDOVATELXNOSTI 
OPERACIJ SLEVA \emph{MOZHNO POLUCHITX} LYUBUYU IZ~$2^n!$ VSEVOZMOZHNYH 
PERESTANOVOK |TIH VAGONOV. (kAZHDYJ STEK DOSTATOCHNO VELIK, I PRI 
NEOBHODIMOSTI V NEGO MOZHNO POMESTITX VSE VAGONY).

\ex[47] v OBOZNACHENIYAH UPR.~2.2.1--4 PRI POMOSHCHI RAZ�EZDOV S 
$n$~STEKAMI MOZHNO POLUCHITX NE BOLEE $a^n_N$~PERESTANOVOK $N$~|LEMENTOV; 
SLEDOVATELXNO, DLYA
\picture{rIS. 31.zhELEZNODOROZHNYJ RAZ�EZD S PYATXYU "STEKAMI".}
POLUCHENIYA VSEH $N!$~PERESTANOVOK TREBUETSYA NE MENEE $\log N!/\log 
a_N\approx \log_4 N$~STEKOV. v UPR.~19 POKAZANO, CHTO NUZHNO NE BOLEE 
$\ceil{\log_2 N}$~STEKOV. kAKOVA ISTINNAYA SKOROSTX ROSTA NEOBHODIMOGO 
CHISLA STEKOV PRI $N\to\infty$?

\ex[23] (e.~dZH.~sMIT.) oB�YASNITE, KAK MOZHNO OBOBSHCHITX ALGORITM~L, CHTOBY ON, 
POMIMO SORTIROVKI, VYCHISLYAL TAKZHE CHISLO \emph{INVERSIJ} V ISHODNOJ PERESTANOVKE.

\subsubchap{rASPREDELYAYUSHCHAYA SORTIROVKA} % 5.2.5
mY PODHODIM TEPERX K INTERESNOMU KLASSU METODOV SORTIROVKI, KOTORYJ, KAK 
POKAZANO V P.~5.4.7, PO SUSHCHESTVU, PRYAMO \emph{PROTIVOPOLOZHEN} SLIYANIYU. 
chITATELYAM, ZNAKOMYM S PERFOKARTOCHNYM OBORUDOVANIEM, HOROSHO IZVESTNA 
|FFEKTIVNAYA PROCEDURA, PRIMENYAEMAYA V MASHINAH DLYA SORTIROVKI KART I 
OSNOVANNAYA NA SRAVNENII CIFR KLYUCHEJ; TU ZHE IDEYU MOZHNO PRISPOSOBITX I 
DLYA PROGRAMMIROVANIYA. oNA OBSHCHEIZVESTNA POD NAZVANIYAMI "PORAZRYADNAYA 
SORTIROVKA", "CIFROVAYA SORTIROVKA" ILI "KARMANNAYA SORTIROVKA".

pREDPOLOZHIM, NAM NUZHNO OTSORTIROVATX KOLODU IZ 52~IGRALXNYH KART. 
oPREDELIM UPORYADOCHENIE PO STARSHINSTVU (DOSTOINSTVU) KART V MASTI
$$
t<2<3<4<5<6<7<8<9<10<v<d<k,
$$
A TAKZHE PO MASTI
$$
\clubsuit<\diamondsuit<\heartsuit<\spadesuit
$$
oDNA KARTA PREDSHESTVUET DRUGOJ, ESLI LIBO (i)~ONA MLADSHE PO MASTI, LIBO 
(ii)~MASTI OBEIH KART ODINAKOVY, NO ONA MLADSHE
%%206
PO DOSTOINSTVU. (eTO CHASTNYJ SLUCHAJ \emph{LEKSIKOGRAFICHESKOGO} 
UPORYADOCHENIYA NA MNOZHESTVE UPORYADOCHENNYH PAR PREDMETOV; SR.~S~UPR.~5--2.) 
tAKIM OBRAZOM,
$$
t\clubsuit<2\clubsuit<\cdots<k\clubsuit<
t\diamondsuit<\cdots<d\spadesuit< k\spadesuit
$$

mY MOGLI BY OTSORTIROVATX KARTY ODNIM IZ OBSUZHDAVSHIHSYA RANEE METODOV; LYUDI,
 KAK PRAVILO, POLXZUYUTSYA SPOSOBOM, PO SUTI ANALOGICHNYM OBMENNOJ 
PORAZRYADNOJ SORTIROVKE. eSTESTVENNO OTSORTIROVATX KARTY SNACHALA PO IH 
MASTI, RAZLOZHIV IH V CHETYRE STOPKI, A ZATEM PEREKLADYVATX KARTY VNUTRI 
KAZHDOJ STOPKI DO TEH POR, POKA ONI NE BUDUT UPORYADOCHENY PO DOSTOINSTVU.

nO SUSHCHESTVUET BOLEE BYSTRYJ SPOSOB! sNACHALA RAZLOZHITX KARTY V 13~STOPOK 
LICEVOJ STORONOJ VVERH PO IH DOSTOINSTVU. zATEM SOBRATX VSE STOPKI VMESTE: 
SNIZU TUZY, ZATEM DVOJKI, TROJKI I T. D. I SVERHU KOROLI (LICEVOJ STORONOJ 
VVERH). pEREVERNUTX KOLODU RUBASHKAMI VVERH I SNOVA RAZLOZHITX, NA 
|TOT RAZ V CHETYRE STOPKI PO MASTI. sLOZHIV VMESTE POLUCHENNYE STOPKI TAK, 
CHTOBY VNIZU BYLI TREFY, ZATEM BUBNY, CHERVI I PIKI, POLUCHIM UPORYADOCHENNUYU 
KOLODU KART.

tA ZHE IDEYA GODITSYA I DLYA SORTIROVKI CHISLOVYH I BUKVENNYH DANNYH. pOCHEMU ZHE 
ONA PRAVILXNA? pOTOMU CHTO (V NASHEM PRIMERE S IGRALXNYMI KARTAMI), ESLI 
DVE KARTY PRI POSLEDNEM RASKLADE POPALI V RAZNYE STOPKI, TO ONI IMEYUT 
RAZNYE MASTI, TAK CHTO KARTA S MENXSHEJ MASTXYU MLADSHE. eSLI ZHE KARTY 
ODNOJ MASTI, TO ONI UZHE NAHODYATSYA V NUZHNOM PORYADKE BLAGODARYA 
PREDVARITELXNOJ SORTIROVKE. iNACHE GOVORYA, PRI VTOROM RASKLADE V KAZHDOJ 
IZ CHETYREH STOPOK KARTY BUDUT RASPOLOZHENY V VOZRASTAYUSHCHEM PORYADKE. eTO 
DOKAZATELXSTVO MOZHNO OBOBSHCHITX I POKAZATX, CHTO TAKIM SPOSOBOM MOZHNO 
OTSORTIROVATX LYUBOE MNOZHESTVO S LEKSIKOGRAFICHESKIM UPORYADOCHENIEM; 
PODROBNOSTI SM. V UPR.~5--2 (V NACHALE GLAVY).

tOLXKO CHTO OPISANNYJ METOD SORTIROVKI SRAZU NE OCHEVIDEN, I NE YASNO, KTO ZHE 
PERVYJ OBNARUZHIL, CHTO ON TAK UDOBEN. v BROSHYURE NA 19~STRANICAH POD 
NAZVANIEM "The Inventory Simplified", OPUBLIKOVANNOJ OTDELENIEM FIRMY IBM 
Tabulating Machines Company V 1923~G., PREDSTAVLEN INTERESNYJ CIFROVOJ 
METOD VYCHISLENIYA SUMM PROIZVEDENIJ NA SORTIROVALXNOJ MASHINE. pUSTX, 
NAPRIMER, NUZHNO PEREMNOZHITX DVA CHISLA, PROBITYH SOOTVETSTVENNO V 
KOLONKAH~1--10 I V KOLONKAH~23--25, I VYCHISLITX SUMMU TAKIH PROIZVEDENIJ 
DLYA BOLXSHOGO CHISLA KART. tOGDA SNACHALA MOZHNO OTSORTIROVATX KARTY PO 
KOLONKE~25 I NAJTI PRI POMOSHCHI SCHETNO-ANALITICHESKOJ MASHINY VELICHINY $a_1$, 
$a_2$,~\dots $a_9$, GDE $a_k$---SUMMA CHISEL IZ KOLONOK 1--10 PO VSEM KARTOCHKAM, 
%%207
NA KOTORYH V KOLONKE~25 PROBITA CIFRA~$k$. zATEM MOZHNO OTSORTIROVATX 
KARTY PO KOLONKE~24 I NAJTI ANALOGICHNYE SUMMY $b_1$, $b_2$,~\dots, $b_9$, 
A POTOM PO KOLONKE~23, POLUCHIV VELICHINY~$c_1$, $c_2$,~\dots, $c_9$. lEGKO 
VIDETX, CHTO ISKOMAYA SUMMA PROIZVEDENIJ RAVNA
$$
a_1+2a_2+\cdots+9a_9+10b_1+20b_2+\cdots+90b_9+
100c_1+200c_2+\cdots+900c_9.
$$
tAKOJ PERFOKARTOCHNYJ METOD TABULIROVANIYA ESTESTVENNYM OBRAZOM PRIVODIT K 
IDEE PORAZRYADNOJ SORTIROVKI "SNACHALA-PO-MLADSHEJ-CIFRE", TAK CHTO, 
PO-VIDIMOMU, ONA VPERVYE STALA IZVESTNA OPERATORAM |TIH MASHIN. pERVAYA 
OPUBLIKOVANNAYA SSYLKA NA |TOT METOD SODERZHITSYA V RANNEJ RABOTE 
l.~dZH.~kOMRI, POSVYASHCHENNOJ OBSUZHDENIYU PERFOKARTOCHNOGO OBORUDOVANIYA 
[Transactions of the Office Machinery Users' Assoc., Ltd. (1929), 25--37,
 OSOBENNO STR. 28].

chTOBY VYPOLNITX PORAZRYADNUYU SORTIROVKU S POMOSHCHXYU evm, NEOBHODIMO RESHITX, 
KAK PREDSTAVLYATX STOPKI. pUSTX IMEETSYA $M$~STOPOK; MOZHNO BYLO BY VYDELITX 
$M$~OBLASTEJ PAMYATI I PERESYLATX KAZHDUYU ISHODNUYU ZAPISX V 
SOOTVETSTVUYUSHCHUYU OBLASTX. nO |TO RESHENIE NAS NE UDOVLETVORYAET, POTOMU CHTO V 
KAZHDOJ OBLASTI DOLZHNO BYTX DOSTATOCHNO MESTA DLYA HRANENIYA $N$~|LEMENTOV, 
I TOGDA POTREBUETSYA PROSTRANSTVO POD $(M+1)N$~ZAPISEJ. tAKAYA CHREZMERNAYA 
POTREBNOSTX V PAMYATI ZASTAVLYALA BOLXSHINSTVO  PROGRAMMISTOV OTKAZYVATXSYA OT 
PRIMENENIYA PORAZRYADNOJ SORTIROVKI NA VYCHISLITELXNYH MASHINAH, POKA 
X.~sXYUVORD [DIPLOMNAYA RABOTA, M.I.t. Digital Computer Laboratory 
Report R-232 (Cambridge Mass: 1954), 25--28] NE POKAZAL, CHTO TOGO 
ZHE |FFEKTA MOZHNO DOBITXSYA, IMEYA V RASPORYAZHENII PROSTRANSTVO VSEGO POD 
$2N$~ZAPISEJ I $M$~SCHETCHIKOV. sDELAV ODIN PREDVARITELXNYJ PROSMOTR 
DANNYH, MOZHNO PROSTO POSCHITATX, SKOLXKO |LEMENTOV POPADET V KAZHDUYU 
OBLASTX; |TO DAST NAM VOZMOZHNOSTX TOCHNO RASPREDELITX PAMYATX POD STOPKI. mY 
UZHE PRIMENYALI |TU IDEYU PRI RASPREDELYAYUSHCHEJ SORTIROVKE (ALGORITM 5.2D).

iTAK, PORAZRYADNUYU SORTIROVKU MOZHNO VYPOLNITX SLEDUYUSHCHIM OBRAZOM: SNACHALA 
PROIZVESTI RASPREDELYAYUSHCHUYU SORTIROVKU \emph{PO MLADSHIM CIFRAM KLYUCHEJ} (V 
SISTEME SCHISLENIYA S OSNOVANIEM~$M$), PEREMESTIV ZAPISI IZ OBLASTI VVODA VO 
VSPOMOGATELXNUYU OBLASTX, ZATEM PROIZVESTI ESHCHE ODNU RASPREDELYAYUSHCHUYU 
SORTIROVKU PO SLEDUYUSHCHEJ CIFRE, PEREMESTIV ZAPISI OBRATNO V ISHODNUYU 
OBLASTX I T. D., DO TEH POR, POKA POSLE ZAVERSHAYUSHCHEGO PROSMOTRA 
(SORTIROVKA PO STARSHEJ CIFRE) VSE KLYUCHI NE OKAZHUTSYA RASPOLOZHENNYMI V 
NUZHNOM PORYADKE.

eSLI U NAS IMEETSYA DESYATICHNAYA MASHINA, A KLYUCHI---12-RAZRYADNYE CHISLA I ESLI 
$N$~VESXMA VELIKO, TO MOZHNO VYBRATX $M=1000$ (SCHITAYA TRI DESYATICHNYE CIFRY 
ZA ODNU V SISTEME SCHISLENIYA S OSNOVANIEM 1000); NEZAVISIMO OT VELICHINY~$N$ 
SORTIROVKA BUDET
%% 208
VYPOLNENA ZA CHETYRE PROSMOTRA. aNALOGICHNO, ESLI BY IMELASX DVOICHNAYA MASHINA,
 A KLYUCHI---40-BITOVYE DVOICHNYE CHISLA, TO MOZHNO POLOZHITX $M=1024$ I TAKZHE 
ZAVERSHITX SORTIROVKU ZA CHETYRE PROSMOTRA. fAKTICHESKI KAZHDYJ PROSMOTR 
SOSTOIT IZ TREH CHASTEJ (PODSCHET, RASPREDELENIE PAMYATI, PEREMESHCHENIE); 
fR|ND [{\sl JACM,\/} {\bf 3} (1956), 151] 
PREDLOZHIL KOMBINIROVATX DVA IZ |TIH TREH DEJSTVIJ, DOBAVIV ESHCHE 
$M$~YACHEEK: NAKAPLIVATX ZNACHENIYA SCHETCHIKOV DLYA $(k+1)\hbox{-GO}$ PROSMOTRA 
ODNOVREMENNO S PEREMESHCHENIEM VO VREMYA $k\hbox{-GO}$ PROSMOTRA.

v TABL.~1 POKAZANO PRIMENENIE PORAZRYADNOJ SORTIROVKI K NASHIM 16~KLYUCHAM PRI 
$M=10$. pRI TAKIH MALYH~$N$ PORAZRYADNAYA SORTIROVKA, KAK PRAVILO, NE 
OSOBENNO POLEZNA, TAK CHTO |TOT MALENXKIJ PRIMER PREDNAZNACHEN GLAVNYM 
OBRAZOM DLYA TOGO, CHTOBY PRODEMONSTRIROVATX DOSTATOCHNOSTX METODA, A NE EGO 
|FFEKTIVNOSTX.

{
\def\subtable#1{
\noalign{
\halign{
##\hfill\bskip&&\bskip\hfill$##$\cr
#1
}}
}
\htable{tABLICA 1}{pORAZRYADNAYA SORTIROVKA}{
#\hfill\bskip&&\bskip$#$\cr
oBLASTX VVODA:           & 503 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 & 154 & 509 & 612 & 677 & 765 & 703 \cr
\subtable{
sCHETCHIKI DLYA MLADSHIH CIFR:           & 1& 1& 2& 3& 1& 2& 1& 3& 1& 1\cr
sOOTVETSTVUYUSHCHEE RASPREDELENIE PAMYATI:& 1& 2& 4& 7& 8&10&11&14&15&16\cr
}
vSPOMOGATELXNAYA OBLASTX: & 170 & 061 & 512 & 612 & 503 & 653 & 703 & 154 & 275 & 765 & 426 & 087 & 897 & 677 & 908 & 509 \cr
\subtable{
sCHETCHIKI DLYA SREDNIH CIFR:           & 4& 2& 1& 0& 0& 2& 2& 3& 1& 1\cr
sOOTVETSTVUYUSHCHEE RASPREDELENIE PAMYATI:& 4& 6& 7& 7& 7& 9&11&14&15&16\cr
}
oBLASTX VVODA;           & 503 & 703 & 908 & 509 & 512 & 612 & 426 & 653 & 154 & 061 & 765 & 170 & 275 & 677 & 087 & 897 \cr
\subtable{
sCHETCHIKI DLYA STARSHIH CIFR:           & 2& 2& 1& 0& 1& 3& 3& 2& 1& 1\cr
sOOTVETSTVUYUSHCHEE RASPREDELENIE PAMYATI:& 2& 4& 5& 5& 6& 9&12&14&15&16\cr
}
vSPOMOGATELXNAYA OBLASTX: & 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
}
}

iSKUSHENNYJ "SOVREMENNYJ" CHITATELX ZAMETIT, ODNAKO, CHTO IDEYA SCHETCHIKOV DLYA 
RASPREDELENIYA PAMYATI PRIVYAZANA K "STAROMODNYM" PONYATIYAM O 
POSLEDOVATELXNOM PREDSTAVLENII DANNYH;
NAM ZHE IZVESTNO, CHTO SPECIALXNO DLYA RABOTY S MNOZHESTVOM TABLIC 
PEREMENNOJ DLINY PRIDUMANO \emph{SVYAZANNOE} RASPREDELENIE. pO|TOMU DLYA 
PORAZRYADNOJ SORTIROVKI ESTESTVENNO BUDET VOSPOLXZOVATXSYA SVYAZANNYMI 
STRUKTURAMI DANNYH. tAK KAK KAZHDAYA STOPKA PROSMATRIVAETSYA POSLEDOVATELXNO, 
TO VSE, CHTO NAM NUZHNO,--- IMETX PRI KAZHDOM |LEMENTE ODNU-EDINSTVENNUYU SSYLKU 
NA SLEDUYUSHCHIJ |LEMENT. kROME TOGO, NIKOGDA NE PRIDETSYA PEREMESHCHATX ZAPISI: 
DOSTATOCHNO SKORREKTIROVATX SVYAZI---I MOZHNO SMELO DVIGATXSYA DALXSHE PO 
SPISKAM. oB�EM NEOBHODIMOJ PAMYATI RAVEN $(1+\varepsilon)N+2\varepsilon 
M$~ZAPISEJ, GDE $\varepsilon$---PROSTRANSTVO, ZANIMAEMOE ODNIM POLEM SVYAZI. 
dOVOLXNO INTERESNY FORMALXNYE PODROBNOSTI |TOJ
%%209
PROCEDURY, POSKOLXKU ONI DAYUT PREKRASNYJ PRIMER TIPICHNYH MANIPULYACIJ SO 
STRUKTURAMI DANNYH, SOEDINYAYUSHCHIH V SEBE POSLEDOVATELXNOE I SVYAZANNOE 
RASPREDELENIE PAMYATI.
\picture{rIS. 32. pORAZRYADNAYA SORTIROVKA SPISKA.}

\alg R.(pORAZRYADNAYA SORTIROVKA SPISKA.) pREDPOLAGAETSYA, CHTO KAZHDAYA IZ 
ZAPISEJ~$R_1$,~\dots, $R_N$ SODERZHIT POLE SVYAZI |LINK|, A KLYUCHI 
PREDSTAVLYAYUT SOBOJ POSLEDOVATELXNOSTX IZ $p$~|LEMENTOV
$$
(a_p, \ldots, a_2, a_1), \quad 0\le a_i<M,
$$
I OTNOSHENIE PORYADKA---LEKSIKOGRAFICHESKOE, T. E.
$$
(a_p, \ldots, a_2, a_1)<(b_p, \ldots, b_2, b_1)
$$
TOGDA I TOLXKO TOGDA, KOGDA SUSHCHESTVUET TAKOJ INDEKS~$j$, $1\le j\le p$, 
CHTO 
$$
a_i=b_i \rem{PRI $i>j$, NO $a_j<b_j$.}
$$
kLYUCHI MOZHNO PREDSTAVLYATX SEBE, V CHASTNOSTI, KAK CHISLA, ZAPISANNYE V  
SISTEME SCHISLENIYA S OSNOVANIEM~$M$:
$$
a_pM^{p-1}+\cdots+a_2M+a_1,
$$
I V |TOM SLUCHAE LEKSIKOGRAFICHESKOE OTNOSHENIE PORYADKA SOOTVETSTVUET 
OBYCHNOMU UPORYADOCHENIYU MNOZHESTVA NEOTRICATELXNYH CHISEL. kLYUCHI TAKZHE MOGUT 
BYTX CEPOCHKAMI BUKV ALFAVITA I T. D.

vO VREMYA SORTIROVKI FORMIRUYUTSYA $M$~"STOPOK" PODOBNO TOMU, KAK |TO 
DELAETSYA V SORTIROVALXNOJ MASHINE DLYA PERFOKART. sTOPKI FAKTICHESKI 
PREDSTAVLYAYUT SOBOJ OCHEREDI V SMYSLE GL.~2, POSKOLXKU MY SVYAZYVAEM IH 
VMESTE TAKIM OBRAZOM, CHTO ONI VSEGDA PROSMATRIVAYUTSYA PO PRINCIPU "PERVYM 
VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA". dLYA KAZHDOJ STOPKI IMEYUTSYA DVE 
PEREMENNYE-UKAZATELI: $|TOP|[i]$ I~$|BOTM|[i]$, $0\le i<M$, I, KAK I V 
GL.~2, PREDPOLAGAETSYA, CHTO
$$
|LINK|(|LOC|(|BOTM|([i])))\equiv|BOTM|[i].
$$
%% 210
\st[cIKL PO~$k$.] vNACHALE USTANOVITX~$|P|\asg|LOC|(R_N)$, UKAZATELX NA 
POSLEDNYUYU ZAPISX. zATEM VYPOLNITX SHAGI S~\stp{2} PO~\stp{6} PRI $k=1$, 2,
~\dots, $p$ (SHAGI S~\stp{2} PO~\stp{6} SOSTAVLYAYUT ODIN "PROSMOTR") I 
ZAVERSHITX RABOTU ALGORITMA. pEREMENNAYA~$|P|$ BUDET UKAZYVATX NA ZAPISX S 
NAIMENXSHIM KLYUCHOM, $|LINK|(|P|)$--- NA  ZAPISX  SO  SLEDUYUSHCHIM  PO  VELICHINE 
KLYUCHOM, $|LINK|(|LINK|(|P|))$---NA SLEDUYUSHCHUYU I T.D.; POLE~$|LINK|$
POSLEDNEJ ZAPISI BUDET RAVNO~$\NULL$.

\st[oPUSTOSHITX STOPKI.] pRI $0\le i<M$ 
USTANOVITX~$|TOP|[i]\asg|LOC|(|BOTM|[i])$ I~$|BOTM|[i]\asg\NULL$.

\st[vYDELITX $k\hbox{-YU}$ CIFRU KLYUCHA.] pUSTX $|KEY|(|P|)$---KLYUCH ZAPISI, NA 
KOTORUYU UKAZYVAET~$|P|$,---RAVEN~$(a_p,~\ldots, a_2, a_1)$; 
USTANOVITX~$i\asg a_k$, $k\hbox{-YA}$ MLADSHAYA CIFRA |TOGO KLYUCHA.

\st[sKORREKTIROVATX SVYAZI.] uSTANOVITX $|LINK|(|TOP|[i])\asg|P|$, ZATEM~$|TOP|[i]\asg|P|$.

\st[pEREJTI K SLEDUYUSHCHEJ ZAPISI.] eSLI $k=1$ (PERVYJ PROSMOTR) I 
ESLI~$|P|=|LOC|(R_j)$ PRI NEKOTOROM~$j\ne1$, TO 
USTANOVITX~$|P|\asg|LOC|(R_{j-1})$ I VOZVRATITXSYA K SHAGU~\stp{3}. 
eSLI $k>1$ (NE PERVYJ PROSMOTR), TO USTANOVITX~$|P|\asg|LINK|(|P|)$ I 
VOZVRATITXSYA K~\stp{3}, ESLI~$|P|\ne\NULL$.

\st[vYPOLNITX ALGORITM~H.] (tEPERX MY UZHE RASPREDELILI VSE |LEMENTY PO 
STOPKAM.) vYPOLNITX PRIVEDENNYJ NIZHE ALGORITM~H, KOTORYJ SCEPLYAET 
OTDELXNYE "STOPKI" V ODIN SPISOK, PODGOTAVLIVAYA IH K SLEDUYUSHCHEMU PROSMOTRU. 
zATEM USTANOVITX~$|P|\asg|BOTM|[0]$, UKAZATELX NA PERVYJ 
|LEMENT OB�EDINENNOGO SPISKA. (sM. UPR.~3.)
\algend
\alg H.(sCEPLENIE OCHEREDEJ.) iZ $M$~DANNYH OCHEREDEJ SO SVYAZYAMI, 
UDOVLETVORYAYUSHCHIMI SOGLASHENIYAM ALGORITMA~R, DANNYJ ALGORITM SOZDAET ODNU 
OCHEREDX, MENYAYA PRI |TOM NE BOLEE $M$~SVYAZEJ. v REZULXTATE $|BOTM|[0]$ 
UKAZYVAET NA PERVYJ |LEMENT, I STOPKA~0 PREDSHESTVUET STOPKE~1, \dots, 
PREDSHESTVUET STOPKE~$(M-1)$.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $i\asg 0$.

\st[uKAZATELX NA VERSHINU STOPKI.] uSTANOVITX $|P|\asg|TOP|[i]$.

\st[sLEDUYUSHCHAYA STOPKA.] uVELICHITX~$i$ NA~1. eSLI $i=M$, TO
USTANOVITX~$|LINK|(|P|)\asg\NULL$ I ZAVERSHITX RABOTU ALGORITMA.

\st[sTOPKA PUSTA?] eSLI $|BOTM|[i]=\NULL$, To VOZVRATITXSYA K~\stp{z}.

\st[sCEPITX STOPKI.] uSTANOVITX $|LINK| (|P|)\asg|BOTM|[i]$. vOZVRATITXSYA K~\stp{2}.
\algend

nA RIS.~33 POKAZANO SODERZHIMOE STOPOK POSLE KAZHDOGO IZ TREH PROSMOTROV, 
VYPOLNYAEMYH PRI SORTIROVKE NASHIH 16~CHISEL S~$M=10$. aLGORITM~R OCHENX 
PROSTO ZAPROGRAMMIROVATX DLYA MASHINY~\MIX, ESLI TOLXKO NAJTI UDOBNYJ, 
SPOSOB IZMENYATX OT PROSMOTRA K PROSMOTRU DEJSTVIYA V SHAGAH~R3 I~R5. v 
SLEDUYUSHCHEJ
%%211
PROGRAMME |TOGO UDALOSX DOBITXSYA, NE ZHERTVUYA SKOROSTXYU VNUTRENNEGO 
CIKLA, PUTEM PREDVARITELXNOJ ZAPISI DVUH KOMAND V TELO PROGRAMMY. zAMETIM, 
CHTO $|TOP|[i]$ I~$|BOTM|[i]$ MOZHNO UPAKOVATX V ODNO SLOVO.

\picture{rIS. 33.               pORAZRYADNAYA SORTIROVKA S ISPOLXZOVANIEM 
SVYAZANNOGO RASPREDELENIYA PAMYATI (POKAZANO SODERZHIMOE VSEH DESYATI STOPOK 
POSLE KAZHDOGO PROSMOTRA).
}
\prog R.(pORAZRYADNAYA SORTIROVKA SPISKOV.) pREDPOLAGAETSYA, CHTO ISHODNYE 
KLYUCHI V YACHEJKAH OT~$|INPUT|+1$ DO~$|INPUT|+N$ SODERZHAT $p=3$~KOMPONENTY 
($a_3$, $a_2$, $a_1$), HRANYASHCHIESYA SOOTVETSTVENNO V POLYAH $(1:1)$, 
$(2:2)$ I~$(3:3)$. (tAKIM OBRAZOM, SCHITAETSYA, CHTO ZNACHENIE~$M$ MENXSHE ILI 
RAVNO RAZMERU BAJTA MASHINY \MIX.) v POLE $(4:5)$ ZAPISI HRANITSYA 
SVYAZX~|LINK|. pUSTX 
$|TOP|[i]\equiv |PILES|+i(l :2)$ I~$|BOTM|[i]\equiv |PILES|+i(4:5)$ PRI 
$0\le i<M$. uDOBNO UKAZYVATX V SVYAZI POLOZHENIE OTNOSITELXNO YACHEJKI |INPUT|,
 TAK CHTO $|LOC|(|BOTM|[i])=|PILES|+i- |INPUT|$; CHTOBY IZBEZHATX
%%212
POYAVLENIYA OTRICATELXNYH SVYAZEJ, NUZHNO RASPOLOZHITX TABLICU~|PILES| 
POSLE TABLICY~|INPUT|. zNACHENIYA INDEKSNYH REGISTROV: $|rI1|\equiv |P|$, 
$|rI2|\equiv i$,  $|rI3|\equiv 3-k$, $|rI4|\equiv|TOP|[i]$; VO VREMYA 
RABOTY ALGORITMA~H $|rI2|\equiv i-M$.
\code
LINK & EQU  & 4:5
TOP  & EQU  & 1:2
START& ENT1 & N  & 1 & R1. cIKL PO $k$. $|P|\asg|LOC|(R_N)$.
     & ENT3 & 2  & 1 & $k\asg 1$.
2H   & ENT2 & M-1& 3 & R2. oPUSTOSHITX STOPKI.
     & ENTA & PILES-INPUT,2 & 3M & $|LOC|(|BOTM|[i])$
     & STA  & PILES,2 (TOP) & 3M & \hfill$\rasg|TOP|[i]$
     & STZ  & PILES,2(LINK) & 3M & $|BOTM|[i]\asg\NULL$.
     & DEC2 & 1             & 3M
     & J2NN & *-4           & 3M & $M>i\ge 0$.
     & LDA  & R3SW,3        & 3
     & STA  & 3F            & 3  &  iZMENITX KOMANDY
     & LDA  & R5SW,3        & 3  &  DLYA $k$-GO PROSMOTRA.
     & STA  & 5F            & 3
3n   & [LD2 & INPUT, 1(3:3)]&    & R3. vYDELITX $k$-YU CIFRU KLYUCHA.
4H   & LD4  & PILES,2 (TOP) & 3N & R4. sKORREKTIROVATX SVYAZI.
     & ST1  & INPUT,4(LINK) & 3N & $|LINK|(|TOP|[i])\asg|P|$.
     & ST1  & PILES,2(TOP)  & 3N & $|TOP|[i]\asg|P|$.
5H   & [DEC1& 1]            &    & R5. pEREJTI K SLEDUYUSHCHEJ ZAPISI.
     & J1NZ & 3B            & 3N & k R3, ESLI PROSMOTR ZAKONCHEN.
6H   & ENN2 & m             & 3  & R6. vYPOLNITX ALGORITM n.
     & JMP  & 7F            & 3  & k n2 S $i\asg0$.
R3SW & LD2  & INPUT, 1(1:1) & N  & kOMANDA DLYA R3 PRI $k=3$.
     & LD2  & INPUT, 1(2:2) & N  & kOMANDA DLYA R3 PRI $k=2$.
     & LD2  & INPUT, 1(3:3) & N  & kOMANDA DLYA R3 PRI $k=1$.
R5SW & LD1  & INPUT, 1(LINK)& N  & kOMANDA DLYA R5 PRI $k=3$.
     & LD1  & INPUT, 1(LINK)& N  & kOMANDA DLYA R5 PRI $k=2$.
     & DEC1 & 1             & N  & kOMANDA DLYA R5 PRI $k=1$.
9H   & LDA  & PILES+M, 2(LINK)& 3M-3 & n4.sTOPKA PUSTA?
     & JAZ  & 8F              & 3M-3 & k    nz,   ESLI $|votm|[i]=\NULL$
%%213
     & STA  & INPUT, 1(LINK)  & 3M-3-E & H5. sCEPITX STOPKI $|LINK|(|P|)\asg|BOTM|[i]$.
7H   & LD1  & PILES+M, 2(TOP) & 3M-E   & H2. uKAZATELX NA VERSHINU STOPKI.
8H   & INC2 & 1               & 3M     & H3. sLEDUYUSHCHAYA STOPKA, $i\asg i+1$.
     & J2NZ & 9B              & 3M     & k n4, ESLI $i\ne M$.
     & STZ  & INPUT, 1(LINK)  & 3      & $|LINK|(|P|)\asg\NULL$.
     & LD1  & PILES (LINK)    & 3      & $|P|\asg|BOTM|[0]$.
     & DEC3 & 1               & 3
     & J3NN & 2B              & 3      & $1\le k\le 3$
\endcode

vREMYA RABOTY PROGRAMMY~R RAVNO $32N+48M+38-4E$, GDE $N$---CHISLO ISHODNYH 
ZAPISEJ, $M$---OSNOVANIE SISTEMY SCHISLENIYA (CHISLO STOPOK), A $E$---CHISLO 
VSTRETIVSHIHSYA PUSTYH STOPOK. sRAVNENIE S DRUGIMI PROGRAMMAMI, 
POSTROENNYMI NA OSNOVE ANALOGICHNYH PREDPOLOZHENIJ (PROGRAMMY~5.2.1m, 
5.2.4L), GOVORIT YAVNO V POLXZU PROGRAMMY~R. vREMYA RABOTY 
$p\hbox{-PROHODNOGO}$ VARIANTA PROGRAMMY~R RAVNO $(11p-1)N+O(pM)$~EDINIC; 
KRITICHESKIJ FAKTOR, VLIYAYUSHCHIJ NA VREMYA RABOTY,---VNUTRENNIJ CIKL, KOTORYJ 
SODERZHIT PYATX OBRASHCHENIJ K PAMYATI I ODIN PEREHOD. dLYA TIPICHNOJ 
VYCHISLITELXNOJ MASHINY $M=b^r$ I~$p=\ceil{t/r}$, GDE $t$--- CHISLO CIFR V 
KLYUCHAH, PREDSTAVLENNYH V SISTEME SCHISLENIYA S OSNOVANIEM~$b$; S ROSTOM~$r$ 
UBYVAET~$p$, TAK CHTO MOZHNO VOSPOLXZOVATXSYA NASHIMI FORMULAMI DLYA 
OPREDELENIYA "NAILUCHSHEGO" ZNACHENIYA~$r$.

eDINSTVENNAYA PEREMENNAYA VELICHINA V FORMULE VREMENI RABOTY---|TO $E$---CHISLO 
PUSTYH STOPOK, OBNARUZHENNYH V SHAGE n4. pREDPOLOZHIM, CHTO VSE 
$M^N$~POSLEDOVATELXNOSTEJ CIFR $M\hbox{-ICHNOJ}$ SISTEMY SCHISLENIYA 
RAVNOVEROYATNY. iZ IZUCHENIYA "POKER-TESTA" V P.~3.3.2D MY UMEEM VYCHISLYATX 
VEROYATNOSTX TOGO, CHTO V KAZHDOM PROSMOTRE VSTRETITSYA ROVNO $M-r$ PUSTYH 
STOPOK; ONA RAVNA
$$
{M(M-1)\ldots(M-r+1)\over M^N}\left\{{N\atop r}\right\},
$$
GDE $\left\{{N\atop r}\right\}$---CHISLO sTIRLINGA VTOROGO RODA. sOGLASNO UPR.
 5,
$$
E=\bigl(\min\max (M-N, 0)p, \ave M(1-{1\over M})^Np,\max(M-1)p\bigr).
$$

v POSLEDNIE GODY POYAVLYAETSYA VSE BOLXSHE "TRUBOPROVODNYH", ILI 
"MAGISTRALXNYH", VYCHISLITELXNYH MASHIN. eTI MASHINY IMEYUT NESKOLXKO 
ARIFMETICHESKIH USTROJSTV I SHEMU "OPEREZHENIYA", TAK CHTO OBRASHCHENIYA K 
PAMYATI I VYCHISLENIYA MOGUT V ZNACHITELXNOJ STEPENI SOVMESHCHATXSYA VO VREMENI; 
NO |FFEKTIVNOSTX
%%214
TAKIH MASHIN ZAMETNO PONIZHAETSYA PRI NALICHII USLOVNYH PEREHODOV, ESLI 
TOLXKO |TI PEREHODY NE PROISHODYAT POCHTI VSEGDA V ODNOM I TOM ZHE 
NAPRAVLENII. vNUTRENNIJ CIKL PORAZRYADNOJ SORTIROVKI HOROSHO PRISPOSOBLEN 
DLYA TAKIH MASHIN, POSKOLXKU |TO PROSTOE ITERATIVNOE VYCHISLENIE, TIPICHNOE 
"PEREZHEVYVANIE CHISEL". pO|TOMU \emph{DLYA MAGISTRALXNYH MASHIN PORAZRYADNAYA 
SORTIROVKA OBYCHNO BYVAET NAIBOLEE |FFEKTIVNYM METODOM IZ VSEH 
IZVESTNYH METODOV VNUTRENNEJ SORTIROVKI}, PRI USLOVII CHTO $N$ NE SLISHKOM 
MALO I KLYUCHI NE SLISHKOM DLINNYE.

rAZUMEETSYA, ESLI KLYUCHI UZH OCHENX DLINNYE, PORAZRYADNAYA SORTIROVKA NE TAK 
|FFEKTIVNA. pREDSTAVXTE SEBE, NAPRIMER, CHTO NUZHNO OTSORTIROVATX PERFOKARTY 
PO KLYUCHU IZ 80~KOLONOK; KAK PRAVILO, VSTRETITSYA OCHENX MALO PAR KART, U 
KOTORYH BY SOVPALI PERVYE PYATX KOLONOK, TAK CHTO PERVYE 75~PROSMOTROV 
VYPOLNYATSYA POCHTI VPUSTUYU. pRI ANALIZE OBMENNOJ PORAZRYADNOJ SORTIROVKI MY 
OBNARUZHILI, CHTO VOVSE NE OBYAZATELXNO PROVERYATX MNOGO BITOV KLYUCHEJ, ESLI 
PROSMATRIVATX IH NE SPRAVA NALEVO, A SLEVA NAPRAVO. pO|TOMU DAVAJTE 
VOZVRATIMSYA K IDEE PORAZRYADNOJ SORTIROVKI, V KOTOROJ KLYUCHI 
PROSMATRIVAYUTSYA, NACHINAYA SO STARSHIH CIFR (sc), A NE S MLADSHIH CIFR (mc).

mY UZHE OTMECHALI, CHTO sc-PORAZRYADNAYA SORTIROVKA ESTESTVENNYM OBRAZOM 
PRIHODIT NA UM. v SAMOM DELE, NETRUDNO PONYATX, POCHEMU PRI SORTIROVKE POCHTY 
V OTDELENIYAH SVYAZI POLXZUYUTSYA IMENNO |TIM METODOM. bOLXSHOE KOLICHESTVO 
PISEM MOZHNO OTSORTIROVATX PO OTDELXNYM MESHKAM, SOOTVETSTVUYUSHCHIM 
GEOGRAFICHESKIM OBLASTYAM; TEPERX KAZHDYJ MESHOK SODERZHIT UZHE MENXSHEE 
KOLICHESTVO PISEM, KOTORYE MOZHNO NEZAVISIMO SORTIROVATX PO DRUGIM MESHKAM, 
SOOTVETSTVUYUSHCHIM VSE MENXSHIM I MENXSHIM GEOGRAFICHESKIM RAJONAM. 
(rAZUMEETSYA, PREZHDE CHEM PODVERGATX PISXMA DALXNEJSHEJ SORTIROVKE, IH 
MOZHNO PEREPRAVITX POBLIZHE K MESTU NAZNACHENIYA.) eTOT PRINCIP "RAZDELYAJ I 
VLASTVUJ" VESXMA PRIVLEKATELEN, I EDINSTVENNAYA PRICHINA EGO NEPRIGODNOSTI 
DLYA SORTIROVKI PERFOKART V TOM, CHTO BOLXSHOE KOLICHESTVO STOPOK PRIVODIT 
K PUTANICE. eTIM ZHE YAVLENIEM OB�YASNYAETSYA OTNOSITELXNAYA |FFEKTIVNOSTX 
ALGORITMA~R (HOTYA ZDESX SNACHALA RASSMATRIVAYUTSYA mc), POTOMU CHTO NAM 
NIKOGDA NE PRIHODITSYA RABOTATX BOLEE CHEM S $M$~STOPKAMI I STOPKI 
PRIHODITSYA SCEPLYATX VSEGO $p$~RAZ. s DRUGOJ STORONY, NETRUDNO POSTROITX 
sc-PORAZRYADNYJ METOD S ISPOLXZOVANIEM SVYAZANNOGO RASPREDELENIYA PAMYATI S 
OTRICATELXNYMI SVYAZYAMI DLYA OBOZNACHENIE GRANIC MEZHDU STOPKAMI, KAK V 
ALGORITME 5.2.4L. (sM. UPR. 10.)

pOZHALUJ, NAILUCHSHIJ KOMPROMISSNYJ VYHOD UKAZAL m.~d.~mAKLAREN [{\sl JACM\/},
 {\bf 13} (1966), 404--411], KOTORYJ PREDLOZHIL ISPOLXZOVATX 
mc-SORTIROVKU, KAK V ALGORITME~R, \emph{NO LISHX V PRIMENENII K STARSHIM 
CIFRAM}. eTO NE BUDET POLNOJ SORTIROVKOJ FAJLA, NO V REZULXTATE FAJL 
STANOVITSYA POCHTI UPORYADOCHENNYM, T. E.
%%215
V NEM OSTAETSYA OCHENX MALO INVERSIJ, TAK CHTO DLYA ZAVERSHENIYA SORTIROVKI 
MOZHNO VOSPOLXZOVATXSYA METODOM PROSTYH VSTAVOK. nASH ANALIZ ALGORITMA 5.2.1m 
PRIMENIM I K-|TOJ SITUACII;
ESLI KLYUCHI RASPREDELENY RAVNOMERNO, TO POSLE SORTIROVKI FAJLA PO STARSHIM 
$p$~CIFRAM V NEM OSTANETSYA V SREDNEM
$$
{1\over 4}N(N-1)M^{-p}
$$
INVERSIJ. [sM. FORMULU~(5.2.1--14) I UPR.~5.2.1--38.] mAKLAREN VYCHISLIL 
SREDNEE CHISLO OBRASHCHENIJ K PAMYATI, PRIHODYASHCHEESYA NA ODIN OBRABATYVAEMYJ 
|LEMENT, I OKAZALOSX, CHTO OPTIMALXNYJ VYBOR ZNACHENIJ~$M$ I~$p$ (V 
PREDPOLOZHENII, CHTO $M$---STEPENX DVOJKI, KLYUCHI RAVNOMERNO RASPREDELENY 
I~$N/M^p\le 0.1$, TAK.CHTO OTKLONENIYA OT RAVNOMERNOGO RASPREDELENIYA 
PRIEMLEMY) OPISYVAETSYA SLEDUYUSHCHEJ TABLICEJ:
\ctable{
\hfill$#$\bskip&&\bskip\hfill$#$\bskip\cr
N= & 100 & 1000 & 5000 & 10000 & 50000 & 100000\cr
\hbox{nAILUCHSHEE } M=& 32 &  128 &  256 &  512 &  1024 &   1024\cr
\hbox{nAILUCHSHEE } p=& 2 & 2 & 2 & 2 & 2  & 2\cr
      \bar \beta(N)=& 19.3 & 18.5 & 18.2 &  18.2 &  18.1 &   18.0 \cr
}
zDESX $\bar\beta(N)$---SREDNEE CHISLO OBRASHCHENIJ K PAMYATI NA ODIN 
SORTIRUEMYJ |LEMENT; |TA VELICHINA OGRANICHENA PRI $N\to\infty$, 
ESLI VZYATX $p=2$ I~$M>\sqrt N$, TAK CHTO SREDNEE VREMYA SORTIROVKI 
ESTX $O(N)$, A NE $O(N \log N)$. eTOT METOD YAVLYAETSYA 
USOVERSHENSTVOVANIEM METODA VSTAVOK V NESKOLXKO SPISKOV (ALGORITM~5.2.1m), 
KOTORYJ, PO SUSHCHESTVU, PREDSTAVLYAET SOBOJ SLUCHAJ $p=1$. v UPR.~12 
PRIVODITSYA INTERESNAYA PROCEDURA mAKLARENA DLYA 
OKONCHATELXNOGO PERERAZMESHCHENIYA POSLE CHASTICHNOJ SORTIROVKI FAJLA S 
ISPOLXZOVANIEM SPISKOV.

eSLI VOSPOLXZOVATXSYA METODAMI ALGORITMA~5.2D I UPR.~5.2-13, TO MOZHNO 
OBOJTISX BEZ POLEJ SVYAZI; PRI |TOM V DOPOLNENIE K PAMYATI, ZANYATOJ SAMIMI 
ZAPISYAMI, POTREBUETSYA VSEGO $O(\sqrt N)$~YACHEEK. eSLI ISHODNYE DANNYE 
RASPREDELENY RAVNOMERNO, TO SREDNEE VREMYA SORTIROVKI PROPORCIONALXNO~$N$.

\excercises
\rex[20] aLGORITM IZ UPR.~5.2--13 POKAZYVAET, KAK MOZHNO VYPOLNITX 
RASPREDELYAYUSHCHUYU SORTIROVKU, IMEYA PROSTRANSTVO PAMYATI VSEGO POD 
$N$~ZAPISEJ (I $M$~POLEJ SCHETCHIKOV), A NE POD $2N$~ZAPISEJ. pRIVODIT LI 
|TA IDEYA K USOVERSHENSTVOVANIYU ALGORITMA PORAZRYADNOJ SORTIROVKI, 
PROILLYUSTRIROVANNOGO V TABL.~1?

\ex[13] yaVLYAETSYA LI ALGORITM~R ALGORITMOM "USTOJCHIVOJ" SORTIROVKI?
%%216

\ex[15] oB�YASNITE, POCHEMU V ALGORITME~H PEREMENNOJ $|BOTM|[0]$ 
PRISVAIVAETSYA ZNACHENIE UKAZATELYA NA PERVUYU ZAPISX V "OB�EDINENNOJ" 
OCHEREDI, 
\emph{NESMOTRYA NA TO CHTO STOPKA 0 MOGLA BYTX PUSTOJ.}

\rex[23] vO VREMYA RABOTY ALGORITMA~R VSE $M$~STOPOK HRANYATSYA V 
VIDE SVYAZANNYH OCHEREDEJ (PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA). 
iSSLEDUJTE IDEYU SVYAZYVANIYA |LEMENTOV STOPOK KAK V \emph{STEKE}. (nA 
RIS.~33 STRELKI POJDUT NE VVERH, A VNIZ, I TABLICA~|BOTM| STANET NE 
NUZHNA.) pOKAZHITE, CHTO ESLI SCEPLYATX STOPKI V SOOTVETSTVUYUSHCHEM PORYADKE, TO 
MOZHET POLUCHITXSYA PRAVILXNYJ METOD SORTIROVKI. bUDET LI |TOT ALGORITM 
BOLEE PROSTYM ILI BOLEE BYSTRYM?

\ex[M24] pUSTX $g_{MN}(z)=\sum p_{MNk}z^k$, GDE $p_{MNk}$--- VEROYATNOSTX 
TOGO, CHTO POSLE SLUCHAJNOGO PROSMOTRA PORAZRYADNOJ SORTIROVKI, RAZLOZHIVSHEGO 
$N$~|LEMENTOV NA $M$~STOPOK, POLUCHILOSX ROVNO $k$~PUSTYH STOPOK. (a) 
pOKAZHITE, CHTO
$g_{M,N+1}(z)=g_{MN}(z)+((1-z)/M)g'_{MN}(z)$. (b) nAJDITE PRI POMOSHCHI 
UKAZANNOGO SOOTNOSHENIYA PROSTYE VYRAZHENIYA DLYA MATEMATICHESKOGO OZHIDANIYA I 
DISPERSII |TOGO RASPREDELENIYA VEROYATNOSTEJ KAK FUNKCIJ OT~$M$ I~$N$.

\ex[20] kAKIE IZMENENIYA NEOBHODIMO VNESTI V PROGRAMMU~R, CHTOBY 
ONA SORTIROVALA NE TREHBAJTOVYE KLYUCHI, A VOSXMIBAJTOVYE? sCHITAETSYA, CHTO 
STARSHIE BAJTY KLYUCHA~$K_i$ HRANYATSYA V YACHEJKE $|KEY|+i(1:5)$, A TRI 
MLADSHIH BAJTA, KAK I RANXSHE,---V YACHEJKE $|INPUT|+i(1:3)$. kAKOVO VREMYA 
RABOTY PROGRAMMY S |TIMI IZMENENIYAMI?

\ex[20] oBSUDITE, V CHEM SOSTOIT SHODSTVO I OTLICHIE ALGORITMA~R I 
ALGORITMA OBMENNOJ PORAZRYADNOJ SORTIROVKI (ALGORITM~5.2.2R).

\rex[20] v ALGORITMAH PORAZRYADNOJ SORTIROVKI, OBSUZHDAVSHIHSYA V TEKSTE,
 PREDPOLAGALOSX, CHTO VSE SORTIRUEMYE KLYUCHI NEOTRICATELXNY. kAKIE 
IZMENENIYA SLEDUET VNESTI V |TI ALGORITMY V TOM SLUCHAE, KOGDA KLYUCHAMI 
MOGUT BYTX I OTRICATELXNYE CHISLA, PREDSTAVLENNYE V \emph{DOPOLNITELXNOM 
ILI OBRATNOM} KODE?

\ex[20] (pRODOLZHENIE UPR.~8.) kAKIE IZMENENIYA NUZHNO VNESTI V |TI 
ALGORITMY V SLUCHAE, KOGDA KLYUCHAMI YAVLYAYUTSYA CHISLA, PREDSTAVLENNYE V 
VIDE ABSOLYUTNOJ VELICHINY SO ZNAKOM?

\ex[30] sKONSTRUIRUJTE ALGORITM PORAZRYADNOJ SORTIROVKI 
"SNACHALA-PO-STARSHEJ-CIFRE", ISPOLXZUYUSHCHIJ SVYAZANNEE RASPREDELENIE. (tAK KAK 
RAZMER PODFAJLOV VSE UMENXSHAETSYA, TO RAZUMNO UMENXSHITX $M$, A DLYA 
SORTIROVKI KOROTKIH FAJLOV PRIMENITX NE PORAZRYADNUYU SORTIROVKU.)

\ex[16] pERESTANOVKA SHESTNADCATI ISHODNYH CHISEL, POKAZANNAYA V TABL.~1,
 SODERZHIT VNACHALE 41 INVERSIYU. pOSLE ZAVERSHENIYA SORTIROVKI INVERSIJ, 
RAZUMEETSYA, NET SOVSEM. sKOLXKO INVERSIJ OSTALOSX BY V FAJLE, ESLI BY 
MY PROPUSTILI PERVYJ PROSMOTR, A VYPOLNILI BY PORAZRYADNUYU SORTIROVKU 
LISHX PO CIFRAM DESYATKOV I SOTEN? sKOLXKO INVERSIJ OSTANETSYA, ESLI 
PROPUSTITX KAK PERVYJ, TAK I VTOROJ PROSMOTRY?

\ex[24] (m. d. mAKLAREN.) pREDPOLOZHIM, ALGORITM~R PRIMENILI TOLXKO K 
$p$~STARSHIM CIFRAM REALXNYH KLYUCHEJ; TOGDA FAJL, ESLI CHITATX EGO PO 
PORYADKU, UKAZANNOMU SVYAZYAMI, POCHTI OTSORTIROVAN, NO KLYUCHI, U KOTORYH 
STARSHIE $p$~CIFR SOVPADAYUT, MOGUT BYTX NEUPORYADOCHENY. pRIDUMAJTE 
ALGORITM PERERAZMESHCHENIYA ZAPISEJ NA TOM ZHE MESTE TAK, CHTOBY KLYUCHI 
RASPOLOZHILISX PO PORYADKU: $K_1\le K_2\le\ldots\le K_N$. [\emph{uKAZANIE:} 
CHASTNYJ SLUCHAJ, KOGDA FAJL POLNOSTXYU OTSORTIROVAN, MOZHNO NAJTI V OTVETE K 
UPR. 5.2--12, EGO MOZHNO SKOMBINIROVATX S PROSTYMI VSTAVKAMI BEZ POTERI 
|FFEKTIVNOSTI, TAK KAK V FAJLE OSTALOSX MALO INVERSIJ.]

\ex[40] rEALIZUJTE METOD VNUTRENNEJ SORTIROVKI, PREDLOZHENNYJ V TEKSTE V 
KONCE |TOGO PUNKTA, POLUCHIV PROGRAMMU SORTIROVKI SLUCHAJNYH DANNYH ZA 
$O(N)$~EDINIC VREMENI, TREBUYUSHCHUYU VSEGO $O(N)$ DOPOLNITELXNYH YACHEEK PAMYATI.

\ex[22] pOSLEDOVATELXNOSTX IGRALXNYH KART
%%217
MOZHNO OTSORTIROVATX V VOZRASTAYUSHCHEM PORYADKE: |t| |2| \dots |v| |d| |k| OT 
VERHNEJ KARTY K NIZHNEJ, ZA DVA PROSMOTRA, RASKLADYVAYA KARTY KAZHDYJ RAZ 
LISHX V DVE STOPKI: RAZLOZHITE KARTY LICEVOJ STORONOJ VNIZ V DVE STOPKI, 
SODERZHASHCHIE SOOTVETSTVENNO |t| |2| |9| |3| |10| I |4| |v| |5| |6| |d| |k| 
|7| |8| (OT NIZHNEJ KARTY K VERHNEJ); ZATEM POLOZHITE VTORUYU STOPKU POVERH 
PERVOJ, POVERNITE KOLODU LICEVOJ STORONOJ VVERH I RAZLOZHITE V DVE STOPKI 
|t| |2| |3| |4| |5| |6| |7| |8| I |9| |10| |v| |d| |k|.  sOEDINITE |TI DVE 
STOPKI I POVERNITE IH LICEVOJ STORONOJ VVERH. kOLODA OTSORTIROVANA.

dOKAZHITE, CHTO PRIVEDENNUYU VYSHE POSLEDOVATELXNOSTX KART NELXZYA 
OTSORTIROVATX V \emph{UBYVAYUSHCHEM} PORYADKE: |k| |d| |v| \dots |2| |t|, OT 
VERHNEJ KARTY K NIZHNEJ, ZA DVA PROSMOTRA, DAZHE ESLI RAZRESHENO RASKLADYVATX 
KARTY V TRI STOPKI. (sDAVATX KARTY, NUZHNO VSEGDA SVERHU KOLODY, 
POVORACHIVAYA IH PRI RAZDACHE RUBASHKOJ VVERH. nA RISUNKE VERHNYAYA KARTA KOLODY 
IZOBRAZHENA SPRAVA, A NIZHNYAYA---SLEVA.)

\ex[m25] rASSMOTRITE ZADACHU IZ UPR.~14 V SLUCHAE, KOGDA KARTY 
RAZDAYUTSYA LICEVOJ STORONOJ VVERH, A NE VNIZ. tAKIM OBRAZOM, ODIN PROSMOTR 
MOZHNO POTRATITX NA PREOBRAZOVANIE VOZRASTAYUSHCHEGO PORYADKA V UBYVAYUSHCHIJ. 
sKOLXKO NUZHNO PROSMOTROV?

\bigskip\epigraph
kAK TOLXKO POYAVITSYA ANALITICHESKAYA MASHINA, ONA, BEZUSLOVNO, OPREDELIT 
DALXNEJSHIJ PUTX RAZVITIYA NAUKI. vSYAKIJ RAZ, KOGDA S EE POMOSHCHXYU BUDET 
NAJDEN KAKOJ-LIBO REZULXTAT, TUT ZHE VOZNIKNET VOPROS: NELXZYA LI TOT ZHE 
REZULXTAT POLUCHITX NA |TOJ MASHINE ZA KRATCHAJSHEE VREMYA?
\signed chARLXZ b|BBIDZH (1864)

%%218
\bye
