\input style
%%150
DLYA SORTIROVKI) BYSTRAYA SORTIROVKA PREVRASHCHAETSYA V OTNYUDX NE BYSTRUYU. vREMYA 
EE RABOTY STANOVITSYA PROPORCIONALXNYM 
$N^2$, A NE $N\log N$ (SM. UPR.~25). v OTLICHIE OT DRUGIH 
ALGORITMOV SORTIROVKI, KOTORYE NAM VSTRECHALISX, ALGORITM Q 
PREDPOCHITAET NEUPORYADOCHENNYE FAJLY!

v UPOMYANUTOJ STATXE hOARA PREDLOZHENY DVA SPOSOBA POPRAVITX SITUACIYU, 
OSNOVYVAYUSHCHIHSYA NA VYBORE LUCHSHEGO ZNACHENIYA PROVERYAEMOGO KLYUCHA $K$, KOTORYJ 
UPRAVLYAET RAZDELENIEM. oDNA IZ EGO REKOMENDACIJ SOSTOIT .V TOM, CHTOBY V 
POSLEDNEJ CHASTI SHAGA Q2 VYBIRATX \emph{SLUCHAJNOE} CELOE CHISLO $q$ MEZHDU 
$l$ I~$r$; V |TOM SHAGE MOZHNO ZAMENITX INSTRUKCII "$K\asg K_l$, $R\asg 
R_l$"  NA
$$
K\asg K_q, \quad R\asg R_q, \quad R_q\asg R_l.
\eqno(27)
$$
sOGLASNO FORMULAM (25), TAKIE SLUCHAJNYE CELYE CHISLA PRIDETSYA VYCHISLYATX V 
SREDNEM LISHX $2(N+1)/(M+2)-1$~RAZ, TAK CHTO DOPOLNITELXNOE VREMYA RABOTY 
NESUSHCHESTVENNO, A SLUCHAJNYJ VYBOR---HOROSHAYA ZASHCHITA OT OPASNOSTI OKAZATXSYA V 
NAIHUDSHEJ SITUACII.

vTOROE PREDLOZHENIE hOARA SOSTOIT V TOM, CHTOBY PROSMOTRETX NEBOLXSHOJ 
UCHASTOK FAJLA I NAJTI MEDIANU DLYA |TOJ SOVOKUPNOSTI DANNYH. tAKOMU 
PODHODU POSLEDOVAL r. k. sINGLTON [{\sl CACM\/}, {\bf 12} (1969), 
185--187], KOTORYJ PREDLOZHIL V KACHESTVE $K_q$  BRATX MEDIANU TREH ZNACHENIJ
$$
K_l, \quad K_{\lfloor(l+r)/2\rfloor}, \quad K_r.
\eqno(28)
$$

pROCEDURA sINGLTONA SOKRASHCHAET CHISLO SRAVNENIJ S $2N \ln N$ PRIMERNO 
DO ${12\over7}N\ln N$ (SM. UPR. 29). mOZHNO POKAZATX, CHTO. V |TOM
SLUCHAE $B_N$ ASIMPTOTICHESKI PRIBLIZHAETSYA K $C_N/5$, A NE K~$C_N/6$, TAK 
CHTO METOD MEDIANY NESKOLXKO UVELICHIVAET VREMYA, ZATRACHIVAEMOE NA 
PERESYLKU DANNYH, PO|TOMU OBSHCHEE VREMYA RABOTY SOKRASHCHAETSYA PRIMERNO, NA 
8\%. (pODROBNYJ ANALIZ SM. V UPR.56.) vREMYA RABOTY V NAIHUDSHEM SLUCHAE VSE 
ESHCHE PORYADKA $N^2$, ODNAKO S TAKIM MEDLENNYM POVEDENIEM ALGORITMA VRYAD LI 
KOGDA-LIBO PRIDETSYA VSTRETITXSYA NA PRAKTIKE.

u.~d.~fR|JZER I a.~ch.~mAK-kELLAR 
[{\sl JACM\/}, {\bf 17} (1970), 496--507] 
PREDLOZHILI RASSMATRIVATX SOVOKUPNOSTX GORAZDO BOLXSHEGO OB�EMA IZ $2^k-1$ 
ZAPISEJ, GDE $k$ VYBIRAETSYA TAK, CHTOBY $2^k\approx N/\ln N$. eTU 
SOVOKUPNOSTX MOZHNO OTSORTIROVATX OBYCHNYM METODOM BYSTROJ SORTIROVKI, POSLE 
CHEGO |LEMENTY VSTAVLYAYUTSYA SREDI OSTALXNYH ZAPISEJ ZA $k$ PROSMOTROV VSEGO 
FAJLA (V REZULXTATE FAJL BUDET RAZDELEN NA $2^k$ PODFAJLOV, OGRANICHENNYH 
|LEMENTAMI PERVONACHALXNOJ SOVOKUPNOSTI). nA ZAKLYUCHITELXNOM 
|TAPE SORTIRUYUTSYA POLUCHENNYE PODFAJLY. sREDNEE CHISLO, SRAVNENIJ,
 VYPOLNYAEMYH TAKOJ PROCEDUROJ "SORTIROVKI SOVOKUPNOSTI", PRIMERNO TAKOE 
ZHE, KAK I DLYA METODA MEDIANY sINGLTONA, KOGDA $N$
%%151
NAHODITSYA V PRAKTICHESKOM DIAPAZONE ZNACHENIJ, NO PRI $N\to\infty$ ONO 
ASIMPTOTICHESKI PRIBLIZHAETSYA K $N\log_2N$.

\section oBMENNAYA PORAZRYADNAYA SORTIROVKA. mY PODHODIM TEPERX K METODU,
 SOVERSHENNO OTLICHNOMU OT VSEH SHEM SORTIROVKI, KOTORYE RASSMATRIVALISX 
PREZHDE; V NEM ISPOLXZUETSYA \emph{DVOICHNOE PREDSTAVLENIE} KLYUCHEJ, 
I.POTOMU ON PREDNAZNACHEN ISKLYUCHITELXNO DLYA DVOICHNYH MASHIN. vMESTO TOGO 
CHTOBY SRAVNIVATX MEZHDU SOBOJ DVA KLYUCHA, V |TOM METODE PROVERYAETSYA, RAVNY 
LI 0 ILI 1 OTDELXNYE BITY KLYUCHA. v DRUGIH OTNOSHENIYAH ON OBLADAET 
HARAKTERISTIKAMI OBMENNOJ SORTIROVKI I NA SAMOM DELE OCHENX NAPOMINAET 
BYSTRUYU SORTIROVKU. tAK KAK ON ZAVISIT OT RAZRYADOV KLYUCHA, 
PREDSTAVLENNOGO V DVOICHNOJ SISTEME SCHISLENIYA, MY NAZYVAEM EGO 
"OBMENNOJ PORAZRYADNOJ SORTIROVKOJ". v OBSHCHIH CHERTAH |TOT ALGORITM MOZHNO 
OPISATX SLEDUYUSHCHIM OBRAZOM:
\enumerate
\li pOSLEDOVATELXNOSTX SORTIRUETSYA \emph{PO STARSHEMU ZNACHASHCHEMU DVOICHNOMU 
BITU} TAK, CHTOBY VSE KLYUCHI, NACHINAYUSHCHIESYA S 0, OKAZALISX PERED VSEMI 
KLYUCHAMI, NACHINAYUSHCHIMISYA S 1. dLYA |TOGO NADO NAJTI SAMYJ LEVYJ KLYUCH $K_i$, 
NACHINAYUSHCHIJSYA S 1, I SAMYJ PRAVYJ KLYUCH $K_j$, NACHINAYUSHCHIJSYA S 0, POSLE CHEGO 
$R_i$ I $R_j$ MENYAYUTSYA MESTAMI, I PROCESS  POVTORYAETSYA, POKA NE STANET $i>j$.

\li pUSTX $F_0$---MNOZHESTVO |LEMENTOV, NACHINAYUSHCHIHSYA S 0, A $F_1$---VSE 
OSTALXNYE. pRIMENIM K $F_0$ PORAZRYADNUYU SORTIROVKU (NACHAV TEPERX SO 
\emph{VTOROGO} BITA SLEVA, A NE SO STARSHEGO) DO TEH POR, POKA MNOZHESTVO 
$F_0$ .NE BUDET POLNOSTXYU OTSORTIROVANO; ZATEM PRODELAEM TO ZHE S $F_1$.
\enumend

nAPRIMER, V TABL.~3 POKAZANO, KAK DEJSTVUET OBMENNAYA PORAZRYADNAYA 
SORTIROVKA NA NASHI 16 SLUCHAJNYH CHISEL, ZAPISANNYH TEPERX V VOSXMERICHNOJ 
SISTEME SCHISLENIYA. nA STADII 1 POKAZAN ISHODNYJ FAJL; POSLE OBMENOV PO 
PERVOMU BITU PRIHODIM KO VTOROJ STADII. nA VTOROJ STADII SORTIRUETSYA 
PERVAYA GRUPPA PO VTOROMU, BITU, NA TRETXEJ---PO TRETXEMU BITU. (chITATELX 
DOLZHEN MYSLENNO PREOBRAZOVATX VOSXMERICHNYE CHISLA V 10-RAZRYADNYE 
DVOICHNYE.) kOGDA MY POSLE SORTIROVKI PO .CHETVERTOMU BITU DOSTIGAEM PYATOJ 
STADII, TO OBNARUZHIVAEM, CHTO KAZHDAYA IZ OSTAVSHIHSYA GRUPP SODERZHIT VSEGO 
PO ODNOMU |LEMENTU,- TAK CHTO |TU CHASTX FAJLA MOZHNO BOLXSHE  NE  
RASSMATRIVATX. zAPISX "${}^4[0232\ 0252]$" OZNACHAET, CHTO PODFAJL $0232\ 
0252$ ESHCHE PREDSTOIT SORTIROVATX PO CHETVERTOMU BITU SLEVA. v |TOM 
KONKRETNOM SLUCHAE SORTIROVKA PO CHETVERTOMU BITU NE DAET NICHEGO NOVOGO; 
CHTOBY RAZDELITX |LEMENTY, NEOBHODIMO DOBRATXSYA DO PYATOGO BITA.

vESX PROCESS SORTIROVKI, POKAZANNYJ V TABL.~3, VYPOLNYAETSYA ZA 22 STADII; 
|TO NESKOLXKO BOLXSHE SOOTVETSTVUYUSHCHEGO CHISLA V BYSTROJ SORTIROVKE (TABL.~2).
 chISLO PROVEROK BITOV 82 TAKZHE VELIKO; NO MY UVIDIM, CHTO CHISLO PROVEROK 
BITOV PRI BOLXSHIH
151
%%152
\picture{tABLICA 3}
%%153
$N$ V DEJSTVITELXNOSTI MENXSHE, CHEM CHISLO SRAVNENIJ V BYSTROJ SORTIROVKE, V 
PREDPOLOZHENII O RAVNOMERNOM RASPREDELENII KLYUCHEJ. oBSHCHEE CHISLO OBMENOV V 
TABL.~3 RAVNO 17, T. E. VESXMA UMERENNO. zAMETIM, CHTO, HOTYA SORTIRUYUTSYA 
10-BITOVYE CHISLA, V DANNOM PRIMERE PRI PROVERKE BITOV NIKOGDA NE 
PRIHODITSYA IDTI DALXSHE SEDXMOGO BITA.

kAK I PRI BYSTROJ SORTIROVKE, DLYA HRANENIYA "INFORMACII O GRANICAH" 
PODFAJLOV, OZHIDAYUSHCHIH SORTIROVKI, MOZHNO VOSPOLXZOVATXSYA STEKOM. vMESTO 
TOGO CHTOBY SORTIROVATX V PERVUYU OCHEREDX NAIMENXSHIJ IZ PODFAJLOV, UDOBNO 
PROSTO PRODVIGATXSYA SLEVA NAPRAVO, TAK KAK RAZMER STEKA V. |TOM SLUCHAE 
NIKOGDA NE PREVZOJDET CHISLA BITOV V SORTIRUEMYH KLYUCHAH. v ALGORITME, 
PRIVEDENNOM NIZHE, |LEMENT STEKA $(r, b)$ UKAZYVAET NA TO, CHTO PODFAJL S 
PRAVOJ GRANICEJ $r$ OZHIDAET SORTIROVKI PO BITU $b$; LEVUYU GRANICU MOZHNO 
NE ZAPOMINATX V STEKE: ONA VSEGDA ZADANA NEYAVNO, POSKOLXKU V |TOJ 
PROCEDURE FAJL VSEGDA OBRABATYVAETSYA SLEVA NAPRAVO.

\alg R.(oBMENNAYA PORAZRYADNAYA SORTIROVKA.) zAPISI $R_1$, \dots, $R_N$ 
PERERAZMESHCHAYUTSYA NA TOM ZHE MESTE; POSLE ZAVERSHENIYA SORTIROVKI IH KLYUCHI 
BUDUT UPORYADOCHENY: $K_1\le \ldots \le K_N$. pREDPOLAGAETSYA, CHTO VSE 
KLYUCHI---$m$-RAZRYADNYE DVOICHNYE CHISLA $(a_1\ a_2\ \ldots\ a_m)_2$; $i$-J PO 
STARSHINSTVU BIT $a_i$ NAZYVAETSYA 
"BIT $i$" KLYUCHA. tREBUETSYA VSPOMOGATELXNYJ STEK, VMESHCHAYUSHCHIJ DO 
$m-1$ |LEMENTOV. eTOT ALGORITM, PO SUSHCHESTVU, SLEDUET PROCEDURE OBMENNOJ 
PORAZRYADNOJ SORTIROVKI S RAZDELENIYAMI, OPISANNOJ VYSHE;
VOZMOZHNY NEKOTORYE USOVERSHENSTVOVANIYA S CELXYU POVYSHENIYA |FFEKTIVNOSTI (ONI 
OPISANY DALEE V TEKSTE I V UPRAZHNENIYAH).

\st[nACHALXNAYA USTANOVKA.] oPUSTOSHITX STEK I USTANOVITX $l\asg 1$, $r\asg 
N$, $b\asg 1$.

\st[nACHATX NOVUYU STADIYU.] (mY HOTELI BY TEPERX OTSORTIROVATX PODFAJL  
$R_l\le \ldots \le R_r$ PO BITU $b$; PO SMYSLU ALGORITMA $l\le r$.) eSLI 
$l=r$, TO PEREJTI K SHAGU \stp{10} (TAK KAK FAJL, SOSTOYASHCHIJ IZ ODNOGO SLOVA,
 UZHE OTSORTIROVAN). v PROTIVNOM SLUCHAE USTANOVITX $i\asg l$, $j\asg r$.

\st[pROVERITX $K_i$ NA 1.] pROVERITX BIT $b$ KLYUCHA $K_i$.. eSLI ON RAVEN 1,
 TO PEREJTI K SHAGU \stp{6}.

\st[uVELICHITX $i$.] uVELICHITX $i$ NA 1. eSLI $i\le j$, TO VOZVRATITXSYA K 
SHAGU \stp{3}; V PROTIVNOM SLUCHAE PEREJTI K SHAGU \stp{8}.

\st[pROVERITX $K_{j+1}$ NA 0.] pROVERITX BIT $b$ KLYUCHA $K_{j+1}$. eSLI ON 
RAVEN 0, TO PEREJTI K SHAGU \stp{7}.

\st[uMENXSHITX $j$.] uMENXSHITX $j$ NA 1. eSLI$ i\le j$, TO PEREJTI K SHAGU 
\stp{5}; V PROTIVNOM SLUCHAE PEREJTI K SHAGU \stp{8}.

\st[pOMENYATX MESTAMI $R_i$, $R_{j+1}$]. pOMENYATX MESTAMI 
$R_i\xchg R_{j+1}$, ZATEM PEREJTI K SHAGU \stp{4}.

\st[pROVERITX OSOBYE SLUCHAI.] (k |TOMU MOMENTU STADIYA RAZDELENIYA
%%154
ZAVERSHENA, $i=j+1$, BIT $b$ KLYUCHEJ~$K_l$, \dots, $K_j$  RAVEN~$0$, 
A BIT~$b$ KLYUCHEJ $K_i$, \dots, $K_r$ RAVEN~$1$.) uVELICHITX $b$ NA~1. eSLI 
$b>m$, GDE $m$---OBSHCHEE CHISLO BITOV V KLYUCHAH, TO PEREJTI K SHAGU~\stp{10}. 
(eTO OZNACHAET, CHTO PODFAJL $R_l$ \dots $R_r$ OTSORTIROVAN. eSLI V FAJLE NE 
MOZHET BYTX RAVNYH KLYUCHEJ, TO TAKUYU PROVERKU MOZHNO NE DELATX.) v PROTIVNOM 
SLUCHAE, ESLI~$j<l$ ILI~$j=r$, VOZVRATITXSYA K SHAGU~\stp{2} (VSE 
PROSMOTRENNYE BITY OKAZALISX RAVNYMI SOOTVETSTVENNO~1 ILI~0). eSLI ZHE 
$j=l$, TO UVELICHITX $l$ NA~1 I PEREJTI K SHAGU~\stp{2} (VSTRETILSYA TOLXKO 
ODIN BIT, RAVNYJ 0).

\st[pOMESTITX V STEK.] pOMESTITX V STEK |LEMENT $(r, b)$, ZATEM USTANOVITX 
$r\asg j$ I PEREJTI K SHAGU \stp{2}.

\st[vZYATX IZ STEKA.] eSLI STEK PUST, TO SORTIROVKA ZAKONCHENA. v 
PROTIVNOM SLUCHAE USTANOVITX $l\asg r+1$, VZYATX IZ. STEKA |LEMENT $(r', 
b')$, USTANOVITX $r\asg r'$, $b\asg b'$ I VOZVRATITXSYA K SHAGU~\stp{2}.
\algend

\prog R.(oBMENNAYA PORAZRYADNAYA SORTIROVKA.) v SLEDUYUSHCHEJ PROGRAMME DLYA 
MASHINY \MIX{} ISPOLXZUYUTSYA, PO SUSHCHESTVU, TE ZHE SOGLASHENIYA, CHTO I V 
PROGRAMME Q. zNACHENIYA REGISTROV: $|rI1|\equiv l-r$, $|rI2|\equiv r$, 
$|rI3|\equiv i$, $|rI4|=j$, $|rI5|\equiv m-b$,  
$|rI6|=\hbox{RAZMER STEKA}$, ESLI NE SCHITATX TOGO, CHTO V NEKOTORYH 
KOMANDAH (OTMECHENNYH NIZHE) UDOBNO OSTAVITX~$|rI3|=i-j$ ILI~$|rI4|=j-i$. 
dVOICHNOJ PRIRODOJ PORAZRYADNOJ SORTIROVKI OB�YASNYAETSYA ISPOLXZOVANIE V |TOJ 
PROGRAMME KOMAND |SRB| (DVOICHNYJ SDVIG SODERZHIMOGO |AX| VPRAVO), |JAE| 
(PEREHOD, ESLI SODERZHIMOE |A| CHETNO) I |JAO| (PEREHOD, ESLI SODERZHIMOE |A| 
NECHETNO), OPREDELENNYH V P.~4.5.2. pREDPOLAGAETSYA, CHTO $N\ge 2$.
\code
START& ENT6 & 0         & 1 & R1. nACHALXNAYA USTANOVKA. oPUSTOSHITX STEK.
     & ENT1 &1-N        & 1 & $l\asg 1$.
     & ENT2 &N          & 1 & $r\asg N$.
     & ENT5 &m-1        & 1 & $b\asg 1$.
     & JMP  &1F         & 1 & k R2 (OPUSTITX PROVERKU $l=r$).
9H   & INC6 &1          & S & R9. pOMESTITX V STEK. [$|rI4|=l-j$]
     & ST2  &STACK,6(A) & S
     & ST5  &STACK,6(v) & S & $(r, b)\Rightarrow\hbox{STEK}$.
     & ENN1 &0,4        & S & $|rI1|\asg l-j$.
     & ENT2 &-1,3       & S & $r\asg j$.
1H   & ENT3 &0,1        & a & R2. nACHATX NOVUYU STADIYU. [$|rI3|=i-j$]
     & ENT4 &0,2        & A & $i\asg l$, $j\asg r$. [$|rI3|=i-j$]
3H   & INC3 &0,4        & C'& R3. pROVERITX $K_i$ NA 1.
     & LDA  &INPUT,3    & C'&
     & SRB  &0,5        & C'& $\hbox{MLADSHIJ BIT |rA|}\asg\hbox{BIT $b$ KLYUCHA $K_i$}$.
%%155
       &JAE   &4F       & C'   & k R4, ESLI ON RAVEN 0.
6n     &DEC4  &1,3      & C''+X& R6. uMENXSHITX $j\asg j-l$. [$|rI4|=j-i$].
       &J4N   &8F       & C''+X& k R8, ESLI $j<i$. [$|rI4|=j-i$]
5n     &INC4  &0,3      & C''  & R5. pROVERITX $K_{j+1}$ NA $0$.
       &LDA   &INPUT+1,4& C''
       &SRB   &0,5      & C''  & $\hbox{MLADSHIJ BIT |rA|}\asg\hbox{BIT $b$ KLYUCHA $K_{j+1}$.}$
       &JAO   &6v       & C''  & k R6, ESLI ON RAVEN 1.
7n     &LDA   &INPUT+1,4& B    & R7. pOMENYATX MESTAMI $R_i$, $R_{j+1}$.
       &LDX   &INPUT,3  & B
       &STX   &INPUT+1,4& B
       &STA   &INPUT,3  & B
4H     &DEC3  &-1,4     & C'-X  & R4. uVELICHITX $i$. $i\asg i+1$. [$|rI3|=i-j$]
       &J3NP  &3B       &C'-X    & k R3, ESLI $i\le j$. [$|rI3|=i-j$]
       &INC3  &0,4      &A-X     & $|rI3|\asg i$.
8n     &J5Z   &0F       &A       & R8.  pROVERITX OSOBYE SLUCHAI. [$|rI4|=\hbox{NEIZVESTEN}$]
       &DEC5  &1        &A-G     & k R10, ESLI $b=m$, INACHE $b\asg b-1$.
       &ENT4  &-1,3     &A-G     &$|rI4|\asg j$.
       &DEC4  &0,2      &A-G     &$|rI4|\asg j-r$.
       &J4Z   &1v       &A-G     & k R2, ESLI $j=r$.
       &DEC4  &0,1      &A-G-R   &$|rI4|\asg j-l$.
       &J4N   &1v       &A-G-R   & k R2, ESLI $j<l$.
       &J4NZ  &9v       &A-G-L-R & k R9, ESLI $j\ne l$.
       &INC1  &1        & K      & $l\asg l+1$.
2n     &J1NZ  &1v       & K+S    & pEREHOD, ESLI $l\ne r$.
0n     &ENT1  &1,2      & S+1    & R10. vZYATX IZ STEKA.
       &LD2   &STACK, 6 (A)& S+1
       &DEC1  &0,2      & S+1
       &LD5   &STACK,6 (v)& S+1  & $\hbox{sTEK}\Rightarrow(r, b)$
       &DEC6  &1        & S+1
       &J6NN  &2v       & S+1    & k R2, ESLI STEK NE BYL PUST.
\endcode
\progend

vREMYA RABOTY PROGRAMMY OBMENNOJ PORAZRYADNOJ SORTIROVKI ZAVISIT OT
$$
\eqalign{
A &=\hbox{CHISLO STADIJ, V KOTORYH $l<r$;}\cr
B &=\hbox{CHISLO ZAMESHCHENIJ;}\cr
C &=C'+C''=\hbox{CHISLO PROVEROK BITOV;}\cr
G&=\hbox{CHISLO SLUCHAEV, KOGDA V SHAGE R8 $b>m$;}\cr
K&=\hbox{CHISLO SLUCHAEV, KOGDA V SHAGE R8 $b\le m$, $j=l$;}\cr
L&=\hbox{CHISLO SLUCHAEV, KOGDA V SHAGE R8 $b\le m$, $j<l$;}\cr
R&=\hbox{CHISLO SLUCHAEV, KOGDA V SHAGE R8 $b\le m$, $j=r$;}\cr
S&=\hbox{CHISLO SLUCHAEV, KOGDA CHTO-LIBO POMESHCHAETSYA V STEK;}\cr
X&=\hbox{CHISLO SLUCHAEV, KOGDA V SHAGE R6 $j<i$.}\cr
}
\eqno(29)
$$
%% 156
pO ZAKONU kIRHGOFA $S=A-G-K-L-R$, TAK CHTO OBSHCHEE VREMYA VYPOLNENIYA  RAVNO 
$27A+8B+8C-23G-14K-17L-19R-X+13$ EDINIC. zA SCHET USLOZHNENIYA PROGRAMMY 
MOZHNO NESKOLXKO USKORITX CIKLY PROVERKI BITOV (SM. UPR.~34). oBMENNUYU 
PORAZRYADNUYU SORTIROVKU MOZHNO TAKZHE USKORITX, ESLI PRI DOSTATOCHNO MALYH 
ZNACHENIYAH RAZNOSTI $r-l$ PRIMENYATX PROSTYE VSTAVKI, KAK |TO SDELANO V 
ALGORITME Q, NO MY NE BUDEM ZADERZHIVATXSYA NA TAKIH USOVERSHENSTVOVANIYAH.

dLYA ANALIZA VREMENI VYPOLNENIYA OBMENNOJ PORAZRYADNOJ SORTIROVKI 
NAPRASHIVAYUTSYA DVA TIPA ISHODNYH DANNYH:
\medskip
\item{i)} pUSTX $N=2^m$ I KLYUCHI, KOTORYE NADO OTSORTIROVATX,--- PROSTO CHISLA 
$0$, $1$, $2$, \dots, $2^m-1$, RASPOLOZHENNYE V SLUCHAJNOM PORYADKE.

\item{ii)} pUSTX $m=\infty$ (NEOGRANICHENNAYA TOCHNOSTX) I KLYUCHI, 
KOTORYE NADO OTSORTIROVATX,---NEZAVISIMYE, RAVNOMERNO RASPREDELENNYE V 
PROMEZHUTKE $[0, 1)$ DEJSTVITELXNYE CHISLA.
\medskip
\noindent
aNALIZ SLUCHAYA~(i) OTNOSITELXNO PROST, PO|TOMU ON OSTAVLEN CHITATELYU V 
KACHESTVE UPRAZHNENIYA (SM. UPR.~35). sLUCHAJ~(ii) SRAVNITELXNO SLOZHEN, 
PO|TOMU ON \emph{TAKZHE} OSTAVLEN DLYA UPRAZHNENIJ. v SLEDUYUSHCHEJ TABLICE 
PRIVEDENY GRUBYE OCENKI REZULXTATOV TOGO I DRUGOGO ANALIZOV:
$$
\matrix{
\hbox{\bf vELICHINA} & \hbox{\bf sLUCHAJ (i)} & \hbox{\bf sLUCHAJ (ii)}\cr
A & N & \alpha N\cr
B & {1\over4} N\log_2N & {1\over4}N\log_2 N\cr
C &  N\log_2N & N\log_2N \cr
G &{1\over2} N & 0 \cr
K & 0 & {1\over2} N\cr
L & 0 &  {1\over2} (\alpha-1)N\cr
R & 0 &  {1\over2} (\alpha-1)N\cr
S & {1\over2}N & {1\over2}N\cr
X & {1\over2}N & {1\over4} (\alpha-1)N\cr
}
\eqno(30)
$$
zDESX $\alpha=1/(\ln 2)=1.4427$. zAMETIM, CHTO SREDNEE CHISLO OBMENOV,
 PROVEROK BITOV I OBRASHCHENIJ K STEKU, PO SUSHCHESTVU, ODINAKOVO V OBOIH 
SLUCHAYAH, NESMOTRYA DAZHE NA TO, CHTO V SLUCHAE (ii) CHISLO STADIJ NA 44\% 
BOLXSHE. nA SORTIROVKU $N$ |LEMENTOV V SLUCHAE (ii) NASHA \MIX-PROGRAMMA 
ZATRATIT V SREDNEM PRIBLIZITELXNO $14.4N\ln N$ EDINIC VREMENI. eTO CHISLO 
MOZHNO BYLO BY SOKRATITX PRIMERNO DO $11.5N\ln N$, ESLI VOSPOLXZOVATXSYA 
PREDLOZHENIEM IZ UPR.~34. sOOTVETSTVUYUSHCHAYA VELICHINA DLYA PROGRAMMY Q RAVNA
%% 157
$12.7N \ln N$, NO I EE MOZHNO UMENXSHITX DO~$11.7 N \ln N$, ESLI 
VOSPOLXZOVATXSYA PREDLOZHENIEM sINGLTONA I VYBIRATX MEDIANU IZ TREH KLYUCHEJ.

v SLUCHAE RAVNOMERNOGO RASPREDELENIYA DANNYH OBMENNAYA PORAZRYADNAYA 
SORTIROVKA ZANIMAET V SREDNEM PRIMERNO STOLXKO ZHE VREMENI, SKOLXKO I 
BYSTRAYA SORTIROVKA; FAKTICHESKI DLYA MASHINY \MIX{} ONA NEMNOGO BYSTREE, CHEM 
BYSTRAYA SORTIROVKA. v UPR.~53 POKAZANO, V KAKOJ MERE ZAMEDLYAETSYA |TOT 
PROCESS PRI NERAVNOMERNOM RASPREDELENII. vAZHNO OTMETITX, CHTO VESX NASH 
ANALIZ OSNOVAN NA PREDPOLOZHENII O TOM. CHTO VSE KLYUCHI RAZLICHNY. 
\emph{06MENNAYA PORAZRYADNAYA SORTIROVKA V TOM VIDE, KAK ONA OPISANA VYSHE, NE 
OCHENX |FFEKTIVNA, ESLI IMEYUTSYA ODINAKOVYE KLYUCHI,} TAK KAK ONA PROHODIT 
CHEREZ NESKOLXKO STADIJ, TREBUYUSHCHIH VREMENI, PYTAYASX RAZDELITX MNOZHESTVA 
ODINAKOVYH KLYUCHEJ, POKA $b$ NE STANET $>m$. oDIN PRIEMLEMYJ SPOSOB 
ISPRAVITX |TOT NEDOSTATOK PREDLOZHEN V OTVETE K UPR.~40.

kAK OBMENNAYA PORAZRYADNAYA SORTIROVKA, TAK I BYSTRAYA SORTIROVKA OSNOVANY 
NA IDEE RAZDELENIYA. zAPISI MENYAYUTSYA MESTAMI DO TEH POR, POKA FAJL NE BUDET 
RAZBIT NA DVE CHASTI: LEVYJ PODFAJL, V KOTOROM VSE KLYUCHI $\le K$ PRI 
NEKOTOROM $K$, I PRAVYJ PODFAJL, V KOTOROM VSE KLYUCHI $\ge K$. v BYSTROJ 
SORTIROVKE V KACHESTVE $K$ VYBIRAETSYA REALXNYJ KLYUCH IZ FAJLA, V TO VREMYA 
KAK V OBMENNOJ PORAZRYADNOJ SORTIROVKE, PO SUSHCHESTVU, VYBIRAETSYA NEKOTORYJ 
ISKUSSTVENNYJ KLYUCH NA OSNOVE DVOICHNYH PREDSTAVLENIJ. chTO KASAETSYA 
ISTORICHESKOJ STORONY DELA, TO OBMENNUYU PORAZRYADNUYU SORTIROVKU OTKRYLI 
p.~hILXDEBRANDT, g.~iSBITC, X.~rAJZING I zh.~shVARC [{\sl JACM\/}, {\bf 6} 
(1959), 156--163] PRIMERNO ZA GOD DO IZOBRETENIYA BYSTROJ SORTIROVKI. 
vOZMOZHNY TAKZHE I DRUGIE SHEMY RAZDELENIYA; NAPRIMER, dZHON mAKKARTI PREDLOZHIL
VYBIRATX $K\approx{1\over2}(u+v)$, ESLI IZVESTNO, CHTO VSE KLYUCHI LEZHAT
V DIAPAZONE MEZHDU $u$ I~$v$.

eSHCHE ODNU STRATEGIYU RAZDELENIYA PREDLOZHIL m.~h.~VAN~eMDEN [{\sl CACM\/}, 
{\bf 13} (1970), 563--567]: VMESTO TOGO CHTOBY VYBIRATX $K$ ZARANEE, MY 
"UZNAEM", KAKOVO MOZHET BYTX HOROSHEE ZNACHENIE $K$, SLEDYA V PROCESSE 
RAZDELENIYA ZA IZMENENIEM VELICHIN 
$K'=\max(K_l, \ldots, K_i)$ I~$K''=\min(K_j, \ldots, K_r)$. mOZHNO 
UVELICHIVATX $i$ DO TEH POR, POKA NE VSTRETITSYA KLYUCH, BOLXSHIJ $K'$; ZATEM 
NACHATX  UMENXSHATX $j$, POKA NE VSTRETITSYA KLYUCH, MENXSHIJ $K''$, POSLE 
CHEGO POMENYATX IH MESTAMI I/ILI UTOCHNITX ZNACHENIYA~$K'$ I~$K''$. 
eMPIRICHESKIE TESTY DLYA |TOJ INTERVALXNOJ SORTIROVKI POKAZYVAYUT, CHTO ONA 
TREBUET OKOLO $1.64N\ln N=1.14N\log_2N$ SRAVNENIJ. eTO EDINSTVENNYJ METOD, 
OBSUZHDAEMYJ V |TOJ KNIGE, DLYA POVEDENIYA KOTOROGO ESHCHE NE NAJDENO 
ADEKVATNOGO TEORETICHESKOGO OB�YASNENIYA.

oBOBSHCHENIE OBMENNOJ PORAZRYADNOJ SORTIROVKI NA SLUCHAJ SISTEMY SCHISLENIYA S 
OSNOVANIEM, BOLXSHIM 2, OBSUZHDAETSYA V P.~5.2.5.
%%158

\section * aSIMPTOTICHESKIE METODY. aNALIZ ALGORITMOV OBMENNOJ SORTIROVKI 
PRIVODIT K NEKOTORYM OSOBENNO POUCHITELXNYM MATEMATICHESKIM ZADACHAM, 
KOTORYE POZVOLYAYUT BOLXSHE UZNATX O SPOSOBAH OPREDELENIYA ASIMPTOTICHESKOGO 
POVEDENIYA FUNKCII. nAPRIMER, PRI ANALIZE METODA PUZYRXKA [FORMULA (9)] MY 
STOLKNULISX S FUNKCIEJ
$$
W_n={1\over n!}\sum_{0\le r <s\le n} s!r^{n-s}.
\eqno(31)
$$
kAKOVO EE ASIMPTOTICHESKOE ZNACHENIE?

mOZHNO DEJSTVOVATX TAK ZHE, KAK PRI ISSLEDOVANII CHISLA INVOLYUCIJ [FORMULA 
(5.1.4--41)]. pO|TOMU, PREZHDE CHEM DVIGATXSYA DALXSHE, POLEZNO ESHCHE RAZ 
PROSMOTRETX OBSUZHDENIE V KONCE P.~5.1.4.

iSSLEDOVANIE FORMULY (31) POKAZYVAET, CHTO VKLAD PRI $s=n$
BOLXSHE, CHEM VKLAD PRI $s=n-1$, I T. D.; |TO NAVODIT NA MYSLX O ZAMENE $s$ 
NA $n-s$. mY SKORO UVIDIM, CHTO NA SAMOM DELE UDOBNEE VSEGO PRIMENITX 
PODSTANOVKI $t=n-s+1$, $m=n+1$, V REZULXTATE KOTORYH FORMULA (31) PRIMET VID
$$
{1\over m}W_{m-1}={1\over m!}\sum_{1\le t< m}(m-t)!\sum_{0\le r<m-t}r^{t-1}.
\eqno(32)
$$
dLYA VNUTRENNEJ SUMMY SUSHCHESTVUET HOROSHO IZVESTNYJ ASIMPTOTICHESKIJ RYAD, 
POLUCHENNYJ IZ FORMULY SUMMIROVANIYA eJLERA:
$$
\eqalign{
\sum_{0\le r<N} r^{t-1} 
&={N^t\over t}-{1\over2}(N^{t-1}-\delta_{t1})+{B_2\over2!}(t-1)(N^{t-2}-\delta_{t2})+\cdots=\cr
&={1\over t}\sum_{0\le j\le k}\perm{t}{j}B_j(N^{t-j}-\delta_{tj})+O(N^{t-k})\cr
}
\eqno(33)
$$

(SM. UPR. 1.2.11.2--4). sLEDOVATELXNO, NASHA ZADACHA SVODITSYA K IZUCHENIYU 
SUMM VIDA
$$
{1\over m!}\sum_{1\le t<m} (m-t)!(m-t)^t\,t^k, \quad k\ge-1.
\eqno(34)
$$
kAK I V P.~5.1.4, MOZHNO POKAZATX, CHTO PRI ZNACHENIYAH $t$, B\'OLXSHIH 
$m^{1/2+\varepsilon}$, CHLENY SUMMY PRENEBREZHIMO MALY: 
$O(\exp(-n^\delta))$. zNACHIT, MOZHNO POLOZHITX $t =O(m^{1/2+\varepsilon})$ I 
ZAMENITX FAKTORIALY PO FORMULE sTIRLINGA
$$
{(m-t)!(m-t)^t\over m!}=
\sqrt{1-{t\over m}}
\exp\left({t\over12m^2}-\left({t^2\over2m}+{t^3\over3m^2}+{t^4\over4m^3}+{t^5\over5m^4}\right)
+O(m^{-2+6\varepsilon})\right).
$$
tAKIM OBRAZOM, NAS INTERESUET ASIMPTOTICHESKOE ZNACHENIE SUMMY
$$
r_k(m)=\sum_{1\le t<m} e^{-t^2/2m}t^k, \quad k\ge-1.
\eqno(35)
$$
%%159
(sUMMIROVANIE ZDESX TAKZHE MOZHNO BYLO BY RASPROSTRANITX NA VESX DIAPAZON 
$1\le t<\infty$, NE IZMENIV PRI |TOM ASIMPTOTICHESKOGO ZNACHENIYA SUMMY, 
POSKOLXKU, KAK UKAZANO VYSHE, VHODYASHCHIE V SUMMU ZNACHENIYA PRI 
$t>m^{1/2+\varepsilon}$ PRENEBREZHIMO MALY.)

pUSTX $g_k(x)=x^ke^{-x^2}$ I~$f_k(x)=g_k(x/\sqrt{2m})$. pO FORMULE 
SUMMIROVANIYA eJLERA PRI~$k\ge 0$
$$
\eqalign{
\sum_{0\le t<m} f_k(t)&=\int_0^m f_k(x)\,dx
+\sum_{1\le j\le p}{B_j\over j!}(f_k^{(j-1)}(m)-f_k^{(j-1)}(0))+R_p,\cr
R_p&={(-1)^{p+1}\over p!}\int_0^m B_p(\{x\})f_k^{(p)}(x)\,dx=\cr
   &\left({1\over\sqrt{2m}}\right)^p 
O\left(\int_0^\infty\abs{g_k^{(p)}(y)}\,dy\right)
=O(m^{-p/2});\cr
}
\eqno(36)
$$
SLEDOVATELXNO, PRI POMOSHCHI, PO SUSHCHESTVU, TEH ZHE PRIEMOV, CHTO I RANXSHE, 
MOZHNO POLUCHITX ASIMPTOTICHESKIJ RYAD DLYA~$r_k(m)$, ESLI TOLXKO $k\ge 0$. nO 
PRI $k=-1$ |TOT METOD NE GODITSYA, TAK KAK ZNACHENIE $f_{-1}(0)$ NE 
OPREDELENO; NELXZYA TAKZHE PROSTO PROSUMMIROVATX OT~$1$ DO~$m$, TAK KAK 
OSTATOCHNYE CHLENY NE DAYUT UBYVAYUSHCHIH STEPENEJ~$m$, ESLI NIZHNIJ PREDEL 
RAVEN~$1$. (iMENNO V |TOM SUTX DELA, I, PREZHDE CHEM DVIGATXSYA DALXSHE, 
CHITATELX DOLZHEN UBEDITXSYA V TOM, CHTO ON HOROSHO PONYAL ZADACHU.)

chTOBY RAZRESHITX |TU DILEMMU, MOZHNO POLOZHITX PO OPREDELENIYU 
$g_{-1}(x)=(e^{-x^2}-1)/x$, $f_{-1}(x)=g_{-1}(x/\sqrt{2m})$; TOGDA 
$f_{-1}(0)=0$ I $r_{-1}(m)$ NETRUDNO POLUCHITX 
IZ~$\sum_{0\le t< m} f_{-1}(t)$. uRAVNENIE (36) SPRAVEDLIVO TEPERX I 
PRI~$k=-1$, A OSTAVSHIJSYA INTEGRAL NAM "HOROSHO ZNAKOM" (SM. UPR. 43):
$$
\eqalign{
{2\over\sqrt{2m}}\int_0^m f_{-1}(x)\,dx&=
   2\int_0^m{e^{-x^2/2m}-1\over x}\,dx=\int_0^{m/2}{e^{-y}-1\over y}\,dy=\cr
&=\int_0^1{e^{-y}-1\over y}\,dy+\int_1^{m/2}{e^{-y}\over y}\,dy-\ln(m/2)=\cr
&=-\gamma-\ln(m/2)+O(e^{-m/2}).\cr
}
$$

tEPERX U NAS DOSTATOCHNO FORMUL I FAKTOV DLYA TOGO, CHTOBY VYVESTI NAKONEC 
OTVET, KOTORYJ RAVEN, KAK POKAZANO V OTVETE K UPR~ 44,
$$
W_n={1\over2}m\ln m+{1\over2}(\gamma+\ln2)m-{2\over3}\sqrt{2\pi m}
+{31\over36}+O(n^{-1/2}), \quad m=n+1.
\eqno(37)
$$
eTIM ZAVERSHAETSYA ANALIZ METODA PUZYRXKA.

%% 160

chTOBY PROANALIZIROVATX OBMENNUYU PORAZRYADNUYU SORTIROVKU, NEOBHODIMO ZNATX 
ASIMPTOTICHESKOE POVEDENIE PRI $n\to\infty$ KONECHNOJ SUMMY
$$
U_n=\sum_{k\ge2}\perm{n}{k}(-1)^k{1\over 2^{k-1}-1}.
\eqno(38)
$$
eTOT VOPROS OKAZYVAETSYA GORAZDO SLOZHNEE DRUGIH ZADACH OB ASIMPTOTICHESKOM 
POVEDENII, S KOTORYMI MY STALKIVALISX DO SIH POR;
|LEMENTARNYE METODY RAZLOZHENIYA V STEPENNYE RYADY, FORMULA SUMMIROVANIYA 
eJLERA I T. D. ZDESX BESSILXNY. sLEDUYUSHCHIJ VYVOD BYL PREDLOZHEN n.~g.~DE~ bREJNOM.

chTOBY IZBAVITXSYA V FORMULE (38) OT PODAVLYAYUSHCHEGO VLIYANIYA
BOLXSHIH MNOZHITELEJ $\perm{n}{k} (-1)^k$, MY NACHNEM S TOGO, CHTO PEREPISHEM 
SUMMU V VIDE BESKONECHNOGO RYADA:
$$
U_n=\sum_{k\ge2}\perm{n}{k}(-1)^k\sum_{j\ge1}\left({1\over2^k-1}\right)^j=
\sum_{j\ge1}(2^j(1-2^{-j})^n-2^j+n).
\eqno(39)
$$

eSLI POLOZHITX $x=n/2^j$, TO CHLEN RYADA ZAPISHETSYA V VIDE
$$
2^j(1-2^{-j})^n-2^j+n=
{n\over x}\left(\left(1-{x\over n}\right)^n-1+x\right).
$$
pRI $x\le n^\varepsilon$ IMEEM
$$
\left(1-{x\over n}\right)^n=\exp\left(n\ln\left(1-{x\over n}\right)\right)
=\exp(-x+x^2O(n^{-1})),
\eqno(40)
$$
A |TO NAVODIT NA MYSLX O TOM, CHTOBY PRIBLIZITX (39) RYADOM
$$
T_n=\sum_{j\ge1}(2^je^{-n/2^j}-2^j+n).
\eqno(41)
$$
chTOBY OPRAVDATX |TO PRIBLIZHENIE, RASSMOTRIM RAZNOSTX 
$U_n-T_n=X_n+Y_n$, GDE
$$
\eqalignno{
X_n&=
\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j<n^{1-\varepsilon}}
    (2^j(1-2^{-j})^n-2^je^{-n/2^j})=
    &\rem{[T.E. SLAGAEMYE PRI $x>n^\varepsilon$]}\cr
&=\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j<n^{1-\varepsilon}} 
    O(ne^{-n/2^j})=
    &\rem{[TAK KAK $0<1-2^{-j}<e^{-2^{-j}}$]}\cr
&=O(n\log n e^{-n^\varepsilon})
    &\rem{[TAK KAK IMEETSYA $O(\log n)$SLAGAEMYH];}\cr
Y_n&=
\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j\ge n^{1-\varepsilon}}
    (2^j(1-2^{-j})^n-2^je^{-n/2^j})=
    &\rem{[SLAGAEMYE PRI $x\le n^{-\varepsilon}$]}\cr
&=\sum_{\scriptstyle j\ge1\atop\scriptstyle 2^j\ge n^{1-\varepsilon}}
    \left(e^{-n/2^j}\left({n\over2^j}\right)O(1)\right)
    &\rem{[PO FORMULE (40)]}\cr
}
$$
%% 161

\bye