\input style
%% 140
RITMA b|TCHERA ZAVERSHAETSYA; |TOT ALGORITM MOZHNO BYLO BY NAZVATX 
SORTIROVKOJ POSREDSTVOM PEREGIBOV!

\MIX-PROGRAMMA DLYA ALGORITMA m PRIVEDENA V UPR.~12. k SOZHALENIYU, 
KOLICHESTVO VSPOMOGATELXNYH OPERACIJ, NEOBHODIMYH DLYA UPRAVLENIYA 
POSLEDOVATELXNOSTXYU SRAVNENIJ, VESXMA VELIKO, TAK CHTO PROGRAMMA MENEE 
|FFEKTIVNA, CHEM DRUGIE METODY, KOTORYE MY RAZBIRALI. oDNAKO ALGORITM 
OBLADAET ODNIM VAZHNYM KOMPENSIRUYUSHCHIM KACHESTVOM: VSE SRAVNENIYA/OBMENY, 
OPREDELYAEMYE DANNOJ ITERACIEJ SHAGA mz, MOZHNO VYPOLNYATX \emph{ODNOVREMENNO} 
NA evm ILI LOGICHESKIH SHEMAH, KOTORYE DOPUSKAYUT PARALLELXNYE
\picture{rIS. 18.  gEOMETRICHESKAYA INTERPRETACIYA METODA b|TCHERA,  $N= 16$.}
VYCHISLENIYA. s TAKIMI PARALLELXNYMI OPERACIYAMI SORTIROVKA VYPOLNYAETSYA ZA  
${1\over 2}\lceil \log_2  N \rceil (\lceil log_2 N \rceil + 1)$ SHAGOV, I 
|TO ODIN
IZ SAMYH BYSTRYH IZVESTNYH OBSHCHIH METODOV. nAPRIMER, \emph{1024 |LEMENTA 
MOZHNO OTSORTIROVATX METODOM b|TCHERA VSEGO ZA 55 PARALLELXNYH SHAGOV}. eGO 
BLIZHAJSHIM SOPERNIKOM YAVLYAETSYA METOD pRATTA (SM. UPR. 5.2.1--30), KOTORYJ 
ZATRACHIVAET 40 ILI 73 SHAGA V ZAVISIMOSTI OT TOGO, KAK SCHITATX: ESLI MY 
GOTOVY DOPUSTITX PEREKRYTIE SRAVNENIJ DO TEH POR, POKA NE POTREBUETSYA 
VYPOLNYATX PEREKRYVAYUSHCHIESYA OBMENY, TO DLYA SORTIROVKI 1024 |LEMENTOV 
METODOM pRATTA TREBUETSYA VSEGO 40 CIKLOV SRAVNENIYA/OBMENA. dALXNEJSHIE 
POYASNENIYA SM. V P.~5.3.4.

\section "bYSTRAYA SORTIROVKA". v METODE b|TCHERA 
POSLEDOVATELXNOSTX SRAVNENIJ PREDOPREDELENA: KAZHDYJ RAZ SRAVNIVAYUTSYA ODNI 
I TE ZHE PARY KLYUCHEJ NEZAVISIMO OT TOGO, CHTO MY MOGLI UZNATX O FAJLE IZ 
PREDYDUSHCHIH SRAVNENIJ. eTO UTVERZHDENIE V BOLXSHOJ MERE SPRAVEDLIVO I 
PRIMENITELXNO K METODU PUZYRXKA, HOTYA ALGORITM v I ISPOLXZUET V 
OGRANICHENNOJ STEPENI POLUCHENNYE SVEDENIYA, S TEM CHTOBY SOKRATITX KOLICHESTVO 
RABOTY V PRAVOM KONCE FAJLA. oBRATIMSYA TEPERX K SOVSEM INOJ STRATEGII, 
PRI KOTOROJ ISPOLXZUETSYA REZULXTAT KAZHDOGO SRAVNENIYA, CHTOBY OPREDELITX, 
KAKIE KLYUCHI SRAVNIVATX SLEDUYUSHCHIMI. tAKAYA STRATEGIYA NE GODITSYA DLYA 
PARALLELXNYH VYCHISLENIJ, NO ONA MOZHET OKAZATXSYA PLODOTVORNOJ DLYA 
VYCHISLITELXNYH MASHIN, RABOTAYUSHCHIH POSLEDOVATELXNO.

%%141

iTAK, RASSMOTRIM. SLEDUYUSHCHUYU SHEMU SRAVNENIJ/OBMENOV. iMEYUTSYA DVA UKAZATELYA 
$i$ I $j$, PRICHEM VNACHALE $i=l$, a $j=N$. sRAVNIM $K_i:K_j$, I ESLI OBMEN 
NE TREBUETSYA, TO UMENXSHIM $j$ NA EDINICU I POVTORIM |TOT PROCESS. pOSLE 
PERVOGO OBMENA UVELICHIM $i$ NA EDINICU I BUDEM PRODOLZHATX SRAVNENIYA, 
UVELICHIVAYA $i$, POKA NE PROIZOJDET ESHCHE ODIN OBMEN. tOGDA OPYATX UMENXSHIM 
$j$ I T. D.; BUDEM "SZHIGATX SVECHKU S OBOIH KONCOV", POKA NE STANET $i=j$. 
pOSMOTRIM, NAPRIMER, CHTO PROIZOJDET S NASHIM FAJLOM IZ SHESTNADCATI CHISEL:
{\catcode`\!=\active\def!#1 {\bf#1}
\def\inci{\noalign{\rightline{UVELICHITX $i$}}}
\def\decj{\noalign{\rightline{UMENXSHITX $j$}}}
\ctable{#&&\bskip\hfill$#$\hfill\bskip\cr
dANO:     &!503 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 & 154 & 509 & 612 & 677 & 765 &!703\cr
\decj
1-J OBMEN &!154 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 &!503 & 509 & 612 & 677 & 765 & 703\cr
\inci
2-J OBMEN & 154 & 087 &!503 & 061 & 908 & 170 & 897 & 275 & 653 & 426 &!512 & 509 & 612 & 677 & 765 & 703\cr
\decj
3-J OBMEN & 154 & 087 &!426 & 061 & 908 & 170 & 897 & 275 & 653 &!503 & 512 & 509 & 612 & 677 & 765 & 703\cr
\inci
4-J OBMEN & 154 & 087 & 426 & 061 &!503 & 170 & 897 & 275 & 653 &!908 & 512 & 509 & 612 & 677 & 765 & 703\cr
\decj
5-J OBMEN & 154 & 087 & 426 & 061 &!275 & 170 & 897 &!503 & 653 & 908 & 512 & 509 & 612 & 677 & 765 & 703\cr
\inci
6-J OBMEN & 154 & 087 & 426 & 061 & 275 & 170 &!503 &!897 & 653 & 808 & 512 & 509 & 612 & 677 & 765 & 703\cr
\decj
}
}
(chTOBY VYYAVITX SOSTOYANIE $i$ I $j$, KLYUCHI $K_i$ I $K_j$ NAPECHATANY ZHIRNYM 
SHRIFTOM.) zAMETIM, CHTO V KAZHDOM SRAVNENII |TOGO PRIMERA UCHASTVUET KLYUCH 
503; VOOBSHCHE V KAZHDOM SRAVNENII BUDET UCHASTVOVATX ISHODNYJ KLYUCH $K_1$, 
POTOMU CHTO ON BUDET PRODOLZHATX OBMENIVATXSYA MESTAMI S DRUGIMI KLYUCHAMI 
KAZHDYJ RAZ, KOGDA MY PEREKLYUCHAEM NAPRAVLENIE. k MOMENTU, KOGDA $i=j$, 
ISHODNAYA ZAPISX $R_1$ ZAJMET SVOYU OKONCHATELXNUYU POZICIYU, POTOMU CHTO, KAK 
NETRUDNO VIDETX, SLEVA  OT NEE NE BUDET BOLXSHIH KLYUCHEJ, A SPRAVA---MENXSHIH. 
iSHODNYJ FAJL OKAZHETSYA RAZDELEN TAKIM OBRAZOM, CHTO PERVONACHALXNAYA ZADACHA 
SVEDETSYA K DVUM BOLEE PROSTYM: SORTIROVKE FAJLA $R_1$ \dots\ $R_{i-1}$ I 
(NEZAVISIMO) SORTIROVKE FAJLA $R_{i+1}$ \dots\ $R_N$. k KAZHDOMU IZ |TIH 
PODFAJLOV MOZHNO PRIMENITX TOT ZHE SAMYJ METOD.

v TABL.~2 POKAZANO, KAK VYBRANNYJ NAMI DLYA PRIMEROV FAJL POLNOSTXYU 
SORTIRUETSYA PRI POMOSHCHI |TOGO METODA ZA 11 STADIJ. v SKOBKI ZAKLYUCHENY 
PODFAJLY, KOTORYE ESHCHE PREDSTOIT OTSORTIROVATX; V MASHINE |TI PODFAJLY 
MOZHNO PREDSTAVLYATX DVUMYA PEREMENNYMI $l$ I~$r$ (GRANICY RASSMATRIVAEMOGO V 
DANNYJ MOMENT FAJLA) I STEKOM DOPOLNITELXNYH PAR $(l_k, r_k)$. kAZHDYJ RAZ, 
KOGDA FAJL PODRAZDELYAETSYA, MY POMESHCHAEM V STEK \emph{BOLXSHIJ} IZ 
PODFAJLOV I NACHINAEM OBRABATYVATX OSTAVSHIJSYA, I TAK DO TEH POR, POKA 
NE PRIDEM K TRIVIALXNO KOROTKIM FAJLAM; KAK POKAZANO V UPR.~20, TAKAYA 
PROCEDURA GARANTIRUET, CHTO V STEKE NIKOGDA NE BUDET NAHODITXSYA BOLEE, CHEM 
PRIMERNO $\log_2 N$ |LEMENTOV.
%% 142
\bye