\input style
\chapnotrue
\chapno=5\subchno=4\subsubchno=6

1) pRIVEDENNYE FORMULY POKAZYVAYUT, CHTO SORTIROVKA YAVLYAETSYA, V SUSHCHNOSTI, 
FUNKCIEJ OT PROIZVEDENIYA~$N$ I~$C$, A NE OT~$N$ I~$C$ POROZNX. zA 
ISKLYUCHENIEM NESKOLXKIH OTNOSITELXNO NEZNACHITELXNYH SOOBRAZHENIJ (NAPRIMER,
 CHTO $B$~VYBIRAETSYA KRATNYM $C$), IZ NASHIH FORMUL SLEDUET, CHTO 
SORTIROVKA ODNOGO MILLIONA ZAPISEJ PO 10 LITER KAZHDAYA ZAJMET PRIMERNO 
STOLXKO ZHE VREMENI, CHTO I SORTIROVKA 100000 ZAPISEJ PO 100 LITER KAZHDAYA. 
nA SAMOM DELE ZDESX MOZHET POYAVITXSYA RAZLICHIE, NE OBNARUZHIMOE V 
NASHIH FORMULAH, TAK KAK VO VREMYA VYBORA S ZAMESHCHENIEM 
NEKOTOROE PROSTRANSTVO ISPOLXZUETSYA DLYA POLEJ SVYAZI. v LYUBOM SLUCHAE RAZMER 
\emph{KLYUCHA} EDVA LI OKAZHET KAKOE-LIBO VLIYANIE, ESLI TOLXKO KLYUCHI NE BUDUT 
STOLX DLINNYMI I SLOZHNYMI, CHTO VNUTRENNIE VYCHISLENIYA NE SMOGUT UGNATXSYA ZA 
LENTAMI.

pRI DLINNYH ZAPISYAH I KOROTKIH KLYUCHAH SOBLAZNITELXNO VYDELITX KLYUCHI, 
OTSORTIROVATX IH, A ZATEM KAK-NIBUDX PERESTAVITX ZAPISI CELIKOM. nO |TA 
IDEYA, KAZHETSYA, NE RABOTAET: ONA MOZHET TOLXKO OTSROCHITX AGONIYU, POSKOLXKU 
PROCEDURA OKONCHATELXNOJ PERESTANOVKI TREBUET POCHTI STOLXKO ZHE VREMENI,
 SKOLXKO POTREBOVALA BY OBSHCHEPRINYATAYA SORTIROVKA SLIYANIEM.

2) mY VIDELI, CHTO TREBUETSYA OT~15 DO~19~MIN, CHTOBY OTSORTIROVATX 
100000~ZAPISEJ PO 100~LITER PRI SOBLYUDENII NASHIH PREDPOLOZHENIJ. sKOLXKO 
VREMENI ZANYALA BY IH SORTIROVKA NA KARTOCHNOM SORTIROVSHCHIKE? eTOT VOPROS 
IMEET PRAKTICHESKIJ INTERES POTOMU, CHTO KARTOCHNYE SORTIROVSHCHIKI DESHEVLE 
evm. dOPUSKAYA, CHTO KAZHDAYA ZAPISX MOZHET BYTX VTISNUTA V 80-KOLONNUYU KARTU 
I CHTO ALFAVITNYJ KLYUCH ZANIMAET SHESTX KOLONOK, PRICHEM
DLYA SORTIROVKI PO KAZHDOJ KOLONKE TREBUETSYA V SREDNEM $1{2\over3}$~PROHODA, 
POLUCHAEM, CHTO MY DOLZHNY PROPUSTITX KAZHDUYU KARTU CHEREZ MASHINU PRIMERNO 
10~RAZ. pRI SKOROSTI 1000 KART V MINUTU |TO ZANYALO BY 1000~MIN, 
T.~E.~POCHTI 17~CH. (iMEETSYA VESXMA BOLXSHAYA VEROYATNOSTX, CHTO ZA |TO VREMYA 
NEKOTORYE KARTY OKAZHUTSYA NECHAYANNO "PEREPUTANNYMI" ILI BUDUT "ZAMYATY" V 
MASHINE.)

3) pRI NAPISANII PROGRAMMY SORTIROVKI, KOTORAYA DOLZHNA ISPOLXZOVATXSYA 
MNOGOKRATNO, RAZUMNO OCHENX TSHCHATELXNO OCENITX VREMYA RABOTY I SRAVNITX 
TEORIYU S DEJSTVITELXNYMI NABLYUDAEMYMI HARAKTERISTIKAMI VYPOLNENIYA. tAK 
KAK TEORIYA SORTIROVKI RAZVITA DOVOLXNO HOROSHO, TO |TA PROCEDURA, KAK 
IZVESTNO, SPOSOBNA VNEZAPNO VYYAVITX DEFEKTY V OBORUDOVANII ILI 
PROGRAMMNOM OBESPECHENII VVODA/VYVODA V SUSHCHESTVUYUSHCHIH 
SISTEMAH. oKAZYVAETSYA OBSLUZHIVANIE RABOTALO MEDLENNEE, CHEM SLEDOVALO, I 
NIKTO |TOGO NE ZAMECHAL, POKA |TO NE PROYAVILOSX NA PROGRAMME SORTIROVKI!

4) nEKOTORYE VYCHISLITELXNYE SISTEMY IMEYUT DVA "BANKA"
%%401
LENTOPROTYAZHNYH USTROJSTV, PRISOEDINENNYH K OTDELXNYM "KANALAM" TAKIM 
SPOSOBOM, CHTO ODNOVREMENNOE CHTENIE I ZAPISX DOPUSKAETSYA TOLXKO DLYA LENT IZ 
RAZNYH BANKOV. dLYA TAKOJ KONFIGURACII BOLXSHE VSEGO PODHODIT 
SBALANSIROVANNOE SLIYANIE. rASSMOTRIM, NAPRIMER, SLUCHAJ SHESTI LENT PO TRI V 
KAZHDOM BANKE I PREDPOLOZHIM, CHTO MY HOTIM VYPOLNITX MNOGOFAZNOE SLIYANIE 
S~$T=6$. vOVREMYA PYATIPUTEVOGO SLIYANIYA DVE IZ VVODNYE LENT BUDUT NE V TOM 
BANKE, TAK CHTO, GRUBO GOVORYA, DVE PYATYH VREMENI VVODA NE BUDUT SOVMESHCHENY S 
VYVODOM. eTO DOBAVLYAET KO VREMENI SORTIROVKI PRIBLIZITELXNO 40\%, TAK CHTO 
SBALANSIROVANNOE SLIYANIE OKAZHETSYA LUCHSHE MNOGOFAZNOGO DAZHE V 
SLUCHAE OBRATNOGO CHTENIYA.

5) nASH ANALIZ VYBORA S ZAMESHCHENIEM BYL VYPOLNEN DLYA "SLUCHAJNYH" FAJLOV, NO 
FAJLY, VSTRECHAYUSHCHIESYA NA PRAKTIKE, OCHENX CHASTO UZHE UPORYADOCHENY V TOJ ILI 
INOJ STEPENI. (fAKTICHESKI INOGDA LYUDI BUDUT SORTIROVATX FAJLY, UZHE 
UPORYADOCHENNYE, TOLXKO CHTOBY UBEDITXSYA V |TOM.) tAKIM OBRAZOM, OPYT DAZHE 
V BOLXSHEJ MERE, CHEM UKAZYVAYUT NASHI FORMULY, POKAZAL, CHTO VYBOR S 
ZAMESHCHENIEM PREDPOCHTITELXNEE DRUGIH VIDOV VNUTRENNEJ SORTIROVKI. eTO 
PREIMUSHCHESTVO NESKOLXKO OSLABLYAETSYA V SLUCHAE MNOGOFAZNOJ SORTIROVKI S 
OBRATNYM CHTENIEM, TAK KAK DOLZHEN BYTX POROZHDEN RYAD UBYVAYUSHCHIH OTREZKOV; NA 
SAMOM DELE r.~l.~gILST|D (ON PERVYJ OPUBLIKOVAL MNOGOFAZNOE 
SLIYANIE) PERVONACHALXNO PO |TOJ PRICHINE OTVERG METOD OBRATNOGO CHTENIYA. nO 
POZDNEE ON ZAMETIL, CHTO CHEREDOVANIE NAPRAVLENIJ BUDET VSE ZHE DAVATX 
DLINNYE VOZRASTAYUSHCHIE OTREZKI. kROME TOGO, MNOGOFAZNYJ METOD S OBRATNYM 
CHTENIEM---|TO EDINSTVENNYJ STANDARTNYJ METOD, KOTORYJ BLAGOSKLONEN K 
UBYVAYUSHCHIM VHODNYM FAJLAM, RAVNO KAK I K VOZRASTAYUSHCHIM.

6) dRUGOE PREIMUSHCHESTVO VYBORA S ZAMESHCHENIEM SOSTOIT V TOM, CHTO |TOT METOD 
DOPUSKAET SOVMESHCHENIE PROCESSOV CHTENIYA, ZAPISI I VYCHISLENIJ. eSLI BY MY 
PROSTO VYPOLNYALI VNUTRENNYUYU SORTIROVKU OCHEVIDNYM SPOSOBOM---ZAPOLNYAYA 
PAMYATX, SORTIRUYA EE I ZATEM ZAPISYVAYA EE PO MERE TOGO, KAK ONA ZAPOLNYAETSYA 
NOVYM SODERZHIMYM,---TO PROHOD RASPREDELENIYA ZANYAL BY PRIMERNO VDVOE BOLXSHE 
VREMENI!

iZ RASSMOTRENNYH NAMI METODOV VNUTRENNEJ SORTIROVKI ESHCHE TOLXKO ODIN MOZHNO 
PRISPOSOBITX K ODNOVREMENNOMU CHTENIYU, ZAPISI I VYCHISLENIYAM---PIRAMIDALXNUYU 
SORTIROVKU. (eTA IDEYA BYLA ISPOLXZOVANA PRI PODGOTOVKE PRIMERA~10 
SHEMY~a.) pREDPOLOZHIM DLYA UDOBSTVA, CHTO VNUTRENNYAYA PAMYATX SODERZHIT 
1000~ZAPISEJ, A KAZHDYJ BLOK NA LENTE---PO 100. dEJSTVOVATX MOZHNO SLEDUYUSHCHIM 
OBRAZOM (CHEREZ $B_1$, $B_2$,~\dots, $B_{10}$ OBOZNACHENO SODERZHIMOE PAMYATI, 
 RAZDELENNOJ NA 10~BLOKOV PO 100~ZAPISEJ).

%% 402

{\sl shAG 0.\/} zAPOLNITX PAMYATX I SDELATX TAK, CHTOBY |LEMENTY $B_2$\dots 
$B_{10}$ UDOVLETVORYALI NERAVENSTVAM PIRAMIDY (S NAIMENXSHIM |LEMENTOM V VERSHINE).

{\sl shAG 1.\/} sVESTI $B_1$\dots$B_{10}$ V PIRAMIDU, ZATEM VYBRATX 
NAIMENXSHIE 100 ZAPISEJ I PEREPISATX IH V $B_{10}$.

{\sl shAG 2.\/} zAPISATX IZ $B_{10}$; V TO ZHE VREMYA VYBRATX NAIMENXSHIE 100 
ZAPISEJ IZ $B_1$\dots$B_{9}$ I POMESTITX IH V $B_9$.

{\sl shAG 3.\/} pROCHITATX V~$B_{10}$ I ZAPISATX IZ $B_9$; V TO ZHE 
VREMYA VYBRATX NAIMENXSHIE 100~ZAPISEJ IZ $B_1$\dots$B_8$ I POMESTITX IH V~$B_8$.

\dots

{\sl shAG 9.\/} pROCHITATX V $B_4$ I ZAPISATX IZ~$B_3$; V TO ZHE 
VREMYA VYBRATX NAIMENXSHIE 100~ZAPISEJ IZ $B_1$ $B_2$, POMESTITX IH V $B_2$ 
I SDELATX TAK, CHTOBY NERAVENSTVA PIRAMIDY BYLI SPRAVEDLIVY DLYA $B_5$\dots$B_{10}$.

{\sl shAG 10.\/} pROCHITATX V~$B_3$ I ZAPISATX IZ~$B_2$, SORTIRUYA~$B_1$, V 
TO ZHE VREMYA SDELATX TAK, CHTOBY NERAVENSTVA PIRAMIDY BYLI SPRAVEDLIVY DLYA $B4$\dots$B_{10}$.

{\sl shAG 11.\/} pROCHITATX V~$B_2$ I ZAPISATX IZ~$B_1$; V TO ZHE 
VREMYA SDELATX TAK, CHTOBY $B_3$\dots$B_{10}$ UDOVLETVORYALI NERAVENSTVAM PIRAMIDY.

{\sl shAG 12.\/} pROCHITATX V~$B_1$, DELAYA TAK, CHTOBY $B_2$\dots$B_{10}$ 
UDOVLETVORYALI NERAVENSTVAM PIRAMIDY. vERNUTXSYA K SHAGU 1. \endmark

7) mY PREDPOLAGAEM, CHTO CHISLO SORTIRUEMYH ZAPISEJ~$N$ NE IZVESTNO ZARANEE. 
nA SAMOM ZHE DELE V BOLXSHINSTVE VYCHISLITELXNYH MASHIN ESTX VOZMOZHNOSTX VSE 
VREMYA SLEDITX ZA CHISLOM ZAPISEJ VO VSEH FAJLAH, I MY MOGLI BY SCHITATX, CHTO 
NASHA VYCHISLITELXNAYA SISTEMA SPOSOBNA SOOBSHCHITX ZNACHENIE~$N$. nASKOLXKO BY 
NAM |TO POMOGLO? k SOZHALENIYU, NE OCHENX! mY VIDELI, CHTO  VYBOR S ZAMESHCHENIEM 
VESXMA VYGODEN, NO ON VEDET K NEPREDSKAZUEMOMU CHISLU NACHALXNYH OTREZKOV. v 
SBALANSIROVANNOM SLIYANII MY MOGLI BY ISPOLXZOVATX INFORMACIYU OB~$N$ DLYA 
USTANOVLENIYA TAKOGO RAZMERA BUFERA~$B$, CHTOBY $S$~OKAZALOSX, SKOREE VSEGO, 
CHUTX MENXSHE STEPENI~$P$; V MNOGOFAZNOM RASPREDELENII S 
OPTIMALXNYM RAZMESHCHENIEM FIKTIVNYH OTREZKOV MY MOGLI BY 
ISPOLXZOVATX INFORMACIYU OB~$N$, CHTOBY RESHITX, KAKOJ UROVENX VYBRATX (SM. 
TABL. 5.4.2-2).

iDYA PO DRUGOMU PUTI I NE ISPOLXZUYA VYBORA S ZAMESHCHENIEM, MY MOGLI BY 
PRIMENITX SLIYANIE V PRYAMOM PORYADKE, OPISANNOE V KONCE P.~5.4.4, VSTROIV 
EGO V OSCILLIRUYUSHCHUYU SORTIROVKU, RASPREDELYAYUSHCHUYU NACHALXNYE OTREZKI 
SOOTVETSTVUYUSHCHEGO NAPRAVLENIYA V SOOTVETSTVUYUSHCHIJ MOMENT (VMESTO TOGO CHTOBY 
BRATX IH S "LENTY~$A$", KAK OPISANO). eTOT METOD, V SUSHCHNOSTI, 
\emph{OPTIMALEN} SREDI VSEH METODOV, VYPOLNYAYUSHCHIH VNUTRENNYUYU SORTIROVKU 
BEZ VYBORA S ZAMESHCHENIEM, TAK KAK ON SLIVAET V SOOTVETSTVII S NAILUCHSHIM 
VOZMOZHNYM $P\hbox{-ARNYM}$ DEREVOM, NO ON VSE ZHE RABOTAET MEDLENNEJ 
METODOV, OSNOVANNYH NA VYBORE S ZAMESHCHENIEM.

%% 403

8) lENTOPROTYAZHNYE USTROJSTVA CHASTO OKAZYVAYUTSYA NAIMENEE NADEZHNYMI CHASTYAMI 
evm. oBSLUZHIVAYUSHCHIJ PERSONAL OBYCHNO POLUCHAET VYZOVY DLYA ISPRAVLENIYA 
LENTOPROTYAZHNYH USTROJSTV CHASHCHE, CHEM DLYA LYUBOGO DRUGOGO KOMPONENTA MASHINY, I 
OPERATORY VYCHISLITELXNOJ MASHINY DOLZHNY UMETX VOZOBNOVLYATX RABOTU POSLE 
SBOYA LENTY. aVTOR NIKOGDA DAZHE NE VIDEL USTANOVOK S~10 ILI BOLEE 
LENTOPROTYAZHNYMI USTROJSTVAMI, KOTORYE BY VSE ODNOVREMENNO NAHODILISX V 
HOROSHEM RABOCHEM SOSTOYANII. sLEDOVATELXNO, MOZHNO PRINYATX ZA AKSIOMU, CHTO 
\emph{ISHODNAYA VVODNAYA LENTA NI V KOEM SLUCHAE NE DOLZHNA IZMENYATXSYA, POKA 
NE STANET IZVESTNO, CHTO VSYA SORTIROVKA UDOVLETVORITELXNO ZAVERSHENA.} v 
NEKOTORYH PRIMERAH SHEMY~A SUSHCHESTVUET DOSADNOE "VREMYA, POKA OPERATOR NE 
SMENIT LENTU", NO BYLO BY SLISHKOM RISKOVANNO ZATIRATX ISHODNYE DANNYE 
VVIDU VOZMOZHNOSTI KAKOJ-LIBO NEISPRAVNOSTI VO VREMYA DLINNOJ SORTIROVKI.

9) pRI PEREHODE OT PRYAMOJ ZAPISI K OBRATNOMU CHTENIYU MY MOZHEM S|KONOMITX 
NEKOTOROE VREMYA, VOVSE NE ZAPISYVAYA POSLEDNIJ BUFER NA LENTU; ON V LYUBOM 
SLUCHAE BUDET VNOVX PROCHITAN! sHEMA~A POKAZYVAET, CHTO |TOT PRIEM V 
DEJSTVITELXNOSTI |KONOMIT SRAVNITELXNO NEMNOGO VREMENI, ZA ISKLYUCHENIEM 
SLUCHAYA OSCILLIRUYUSHCHEJ SORTIROVKI, KOGDA NAPRAVLENIYA MENYAYUTSYA CHASTO.

10) eSLI V NASHEM RASPORYAZHENII MNOGO LENTOCHNYH USTROJSTV, TO NE VSEGDA 
STOIT ISPOLXZOVATX IH VSE V CELYAH POLUCHENIYA "VYSOKOGO PORYADKA SLIYANIYA". 
tAK, NAPRIMER, BOLEE VYSOKIJ PORYADOK SLIYANIYA OBYCHNO OZNACHAET MENXSHIJ 
RAZMER BLOKA, A PROCENTNAYA RAZNOSTX MEZHDU $\log_P S$ I~$\log_{P+1} S$ NE 
OCHENX VELIKA PRI BOLXSHIH~$P$. pODUMAJTE TAKZHE O BEDNOM OPERATORE evm, 
KOTORYJ DOLZHEN USTANOVITX VSE |TI RABOCHIE LENTY. s DRUGOJ STORONY, V 
UPR.~12 OPISAN INTERESNYJ SPOSOB ISPOLXZOVANIYA DOPOLNITELXNYH 
LENTOPROTYAZHNYH USTROJSTV, GRUPPIRUEMYH TAK. CHTOBY SOVMESTITX VREMYA VVODA 
I VYVODA BEZ UVELICHENIYA PORYADKA SLIYANIYA.

11) nA MASHINAH, PODOBNYH \MIX, KOTORYE IMEYUT FIKSIROVANNYJ I DOVOLXNO 
MALENXKIJ RAZMER BLOKOV, DLYA SLIYANIYA EDVA LI TREBUETSYA MNOGO VNUTRENNEJ 
PAMYATI. zDESX OSCILLIRUYUSHCHAYA SORTIROVKA BOLEE PREDPOCHTITELXNA; pOTOMU CHTO 
STANOVITSYA VOZMOZHNYM SOHRANYATX DEREVO VYBORA S ZAMESHCHENIEM V PAMYATI VO 
VREMYA SLIYANIYA. nA SAMOM DELE V |TOM SLUCHAE MOZHNO 
USOVERSHENSTVOVATX OSCILLIRUYUSHCHUYU SORTIROVKU (KAK PREDLOZHIL k.~dZH.~bELL V 
1962~G.), SLIVAYA NOVYJ NACHALXNYJ OTREZOK V VYVOD KAZHDYJ RAZ, KOGDA MY 
SLIVAEM S RABOCHIH LENT!

12) mY VIDELI, CHTO FAJLY NA NESKOLXKIH BOBINAH DOLZHNY SORTIROVATXSYA 
POSLEDOVATELXNO BOBINA ZA BOBINOJ, CHTOBY IZBEZHATX CHREZMERNOJ RABOTY PO 
PERESTANOVKE LENT. fAKTICHESKI SBALANSIROVANNOE SLIYANIE S SHESTXYU LENTAMI, 
ESLI ONO TSHCHATELXNO
%% 404
ZAPROGRAMMIROVANO, MOZHET SORTIROVATX \emph{TRI} BOBINY DO 
MOMENTA OKONCHATELXNOGO SLIYANIYA.

dLYA SLIYANIYA OTNOSITELXNO BOLXSHOGO CHISLA OTDELXNO OTSORTIROVANNYH BOBIN 
BYSTREJSHIM BUDET DEREVO SLIYANIYA S MINIMALXNOJ DLINOJ PUTI (SR. 
S~P.~5.4.4). eTO POSTROENIE BYLO VPERVYE OSUSHCHESTVLENO e.~X.~fR|NDOM [{\sl 
JACM\/}, {\bf 3}(1956), 166--167] I ZATEM u.~X.~bURZHEM [{\sl Information 
and Control,\/} {\bf 1} (1958), 181--197], KOTORYE OTMETILI, CHTO 
OPTIMALXNYJ SPOSOB SLIYANIYA OTREZKOV DANNYH (VOZMOZHNO, NERAVNYH) DLIN 
POLUCHAETSYA S POMOSHCHXYU POSTROENIYA DEREVA S MINIMALXNOJ \emph{VZVESHENNOJ} 
DLINOJ PUTI, ISPOLXZUYA DLINY OTREZKOV V KACHESTVE VESOV (SM.~P.~2.3.4.5 
I~5.4.9), ESLI PRENEBRECHX VREMENEM USTANOVKI LENT. nO FAJLY, ZANIMAYUSHCHIE 
NESKOLXKO BOBIN, VEROYATNO, SLEDUET HRANITX NA DISKAH ILI DRUGOM 
ZAPOMINAYUSHCHEM USTROJSTVE BOLXSHOJ EMKOSTI, A NE NA LENTAH.

13) v NASHEM OBSUZHDENII MY, NE ZADUMYVAYASX, PREDPOLAGALI, CHTO IMEETSYA 
VOZMOZHNOSTX ISPOLXZOVATX NEPOSREDSTVENNO INSTRUKCII VVODA/VYVODA I CHTO 
NIKAKOJ SLOZHNYJ SISTEMNYJ INTERFEJS NE MESHAET NAM ISPOLXZOVATX LENTY S 
TAKOJ |FFEKTIVNOSTXYU, NA KAKUYU RASSCHITYVALI KONSTRUKTORY APPARATURY. eTI 
IDEALXNYE PREDPOLOZHENIYA POZVOLILI NAM PRONIKNUTX V SUTX PROBLEM SLIYANIYA, 
I ONI MOGUT DATX NEKOTORYJ PODHOD K KONSTRUIROVANIYU SOOTVETSTVUYUSHCHIH 
OPERACIONNYH SISTEM. oDNAKO SLEDUET PONIMATX, CHTO MULXTIPROGRAMMIROVANIE 
I MULXTIPROCESSIROVANIE MOGUT ZNACHITELXNO USLOZHNITX SITUACIYU.

14) oBSUZHDAEMYE NAMI VOPROSY BYLI VPERVYE RASSMOTRENY V PECHATI 
e.~X.~fR|NDOM [{\sl JACM,\/} {\bf 3} (1956), 134--165],u.~zOBERBXEROM 
[{\sl Electron. Datenverarb.,\/} {\bf 5} (1960), 28--44] I m.~a.~gOTCEM 
[Digital Computer User's Handbook (New York, McGraw-Hill, 1967) 1.292--1.320].

\section rEZYUME. mY MOZHEM SLEDUYUSHCHIM OBRAZOM VKRATCE VYRAZITV VSE, CHTO 
UZNALI O SRAVNENII RAZLICHNYH SHEM SLIYANIYA:

\proclaim tEOREMA a. tRUDNO RESHITX, KAKAYA SHEMA SLIYANIYA YAVLYAETSYA 
NAILUCHSHEJ V KONKRETNOJ SITUACII. \endmark

pRIMERY, KOTORYE MY VIDELI NA SHEME~a, POKAZYVAYUT, KAK 100000~ZAPISEJ PO 
100~LITER (ILI 1~MILLION ZAPISEJ PO 10~LITER), RASPOLOZHENNYH V SLUCHAJNOM 
PORYADKE, MOGLI BY BYTX OTSORTIROVANY S ISPOLXZOVANIEM SHESTI LENT PRI 
DOSTATOCHNO REALISTICHESKIH PREDPOLOZHENIYAH. eTI DANNYE ZANIMAYUT OKOLO 
POLOVINY LENTY I MOGUT BYTX OTSORTIROVANY PRIBLIZITELXNO ZA 15--19 MIN;
ODNAKO SUSHCHESTVUYUSHCHEE LENTOCHNOE OBORUDOVANIE SILXNO RAZLICHAETSYA PO 
VOZMOZHNOSTYAM, I VREMYA VYPOLNENIYA TAKOJ RABOTY NA RAZNYH MASHINAH IZMENYAETSYA 
V DIAPAZONE PRIBLIZITELXNO OT~
%%405
CHETYREH MINUT DO~DVUH CHASOV. v NASHIH PRIMERAH OKOLO 3~MIN RASHODUETSYA NA 
NACHALXNOE RASPREDELENIE OTREZKOV I VNUTRENNYUYU SORTIROVKU, OKOLO 4.5~MIN---NA 
OKONCHATELXNOE SLIYANIE I PEREMOTKU VYVODNOJ LENTY I OKOLO 
7.5--11.5~MIN---NA PROMEZHUTOCHNYE STADII SLIYANIYA.

eSLI IMEETSYA SHESTX LENT, KOTORYE NELXZYA CHITATX V OBRATNOM NAPRAVLENII, TO 
NAILUCHSHIM METODOM SORTIROVKI PRI NASHIH PREDPOLOZHENIYAH BYLO "MNOGOFAZNOE 
SLIYANIE S RASSHCHEPLENIEM LENT" (PRIMER~4), A DLYA LENT, DOPUSKAYUSHCHIH OBRATNOE 
CHTENIE, NAILUCHSHIM METODOV OKAZALSYA MNOGOFAZNYJ METOD S OBRATNYM CHTENIEM SO 
SLOZHNYM RAZMESHCHENIEM FIKTIVNYH OTREZKOV (PRIMER~7). oSCILLIRUYUSHCHAYA 
SORTIROVKA (PRIMER~9) ZANIMAET VTOROE MESTO. v OBOIH SLUCHAYAH KASKADNOE 
SLIYANIE BOLEE PROSTO I LISHX NEZNACHITELXNO MEDLENNEE (PRIMERY~5 I~8). v 
SLUCHAE PRYAMOGO CHTENIYA OBYCHNOE SBALANSIROVANNOE SLIYANIE (PRIMER~1) 
OKAZALOSX UDIVITELXNO |FFEKTIVNYM, CHASTICHNO IZ-ZA UDACHI V |TOM 
KONKRETNOM PRIMERE, A CHASTICHNO IZ-ZA TOGO, CHTO ONO TRATIT 
SRAVNITELXNO MALO VREMENI NA PEREMOTKU.

pOLOZHENIE NESKOLXKO IZMENILOSX BY, ESLI BY V NASHEM RASPORYAZHENII BYLO 
DRUGOE CHISLO LENT.

\section gENERATORY SORTIROVKI. v USLOVIYAH BOLXSHOGO 
RAZNOOBRAZIYA HARAKTERISTIK DANNYH I OBORUDOVANIYA POCHTI NEVOZMOZHNO 
NAPISATX EDINSTVENNUYU PROGRAMMU VNESHNEJ SORTIROVKI, KOTORAYA BYLA BY 
UDOVLETVORITELXNOJ V PODAVLYAYUSHCHEM BOLXSHINSTVE SLUCHAEV. tAKZHE VESXMA 
TRUDNO SOZDATX PROGRAMMU, KOTORAYA V REALXNYH USLOVIYAH |FFEKTIVNO 
RABOTAET S LENTAMI. sLEDOVATELXNO, IZGOTOVLENIE PROGRAMMNOGO OBESPECHENIYA 
SORTIROVKI---SAMOSTOYATELXNAYA ZADACHA, TREBUYUSHCHAYA BOLXSHOJ RABOTY. 
\dfn{gENERATOR SORTIROVKI}---|TO PROGRAMMA, KOTORAYA, OSNOVYVAYASX NA 
PARAMETRAH, OPISYVAYUSHCHIH FORMAT DANNYH I KONFIGURACIYU OBORUDOVANIYA,
 POROZHDAET MASHINNUYU PROGRAMMU, SPECIALXNO PRISPOSOBLENNUYU K KONKRETNOMU 
PRIMENENIYU SORTIROVKI. pODOBNAYA PROGRAMMA CHASTO SVYAZANA S YAZYKAMI VYSOKOGO 
UROVNYA, TAKIMI, KAK~kOBOL ILI~PL/1, ILI ONA MOZHET BYTX NAPISANA KAK NABOR 
MAKROOPREDELENIJ DLYA ISPOLXZOVANIYA SOVMESTNO S MAKROASSEMBLEROM.

oDNOJ IZ OSOBENNOSTEJ, OBYCHNO OBESPECHIVAEMYH GENERATOROM SORTIROVKI, 
YAVLYAETSYA VOZMOZHNOSTX VSTAVLYATX "SOBSTVENNYE KOMANDY"---OSOBYE INSTRUKCII, 
KOTORYE DOLZHNY VKLYUCHATXSYA V PERVYJ I POSLEDNIJ PROHODY PROGRAMMY 
SORTIROVKI. sOBSTVENNYE KOMANDY PERVOGO PROHODA OBYCHNO ISPOLXZUYUTSYA, 
CHTOBY OTREDAKTIROVATX ISHODNYE ZAPISI, CHASTO SOKRASHCHAYA IH ILI 
NEZNACHITELXNO UDLINYAYA, CHTOBY PRIVESTI IH K FORME, BOLEE PROSTOJ DLYA 
SORTIROVKI. pUSTX, NAPRIMER, ISHODNYE ZAPISI DOLZHNY BYTX OTSORTIROVANY PO 
DEVYATILITERNOMU KLYUCHU, IZOBRAZHAYUSHCHEMU DATU V FORMATE MESYAC-DENX-GOD:
%%406
$$
|JUL04| \ |OCT311517| \ |NOV051605| \ |JUL141789| \ |NOV201917|
$$
tREHBUKVENNYE KODY MESYACEV MOZHNO NAJTI V TABLICE I ZAMENITX CHISLAMI, 
PRICHEM NAIBOLEE ZNACHASHCHIE POLYA MOGUT BYTX POMESHCHENY SLEVA:
$$
|17760704| \ |15171031| \ |16051105| \ |17890714| \ |19171120|
$$
eTO UMENXSHAET DLINU ZAPISEJ I DELAET BOLEE PROSTYM POSLEDUYUSHCHEE SRAVNENIE.
 (kOD KLYUCHEJ MOG BY BYTX SDELAN DAZHE BOLEE KOMPAKTNYM.) sOBSTVENNYE 
KOMANDY POSLEDNEGO PROHODA MOGUT ISPOLXZOVATXSYA DLYA VOSSTANOVLENIYA 
ISHODNOGO FORMATA I/ILI DLYA VNESENIYA DRUGIH ZHELATELXNYH IZMENENIJ V FAJL 
I/ILI DLYA VYCHISLENIYA KAKOJ-LIBO FUNKCII OT VYVODNYH ZAPISEJ. aLGORITMY 
SLIYANIYA, KOTORYE MY IZUCHILI, ORGANIZOVANY TAKIM OBRAZOM, CHTO POSLEDNIJ 
PROHOD LEGKO OTLICHITX OT OSTALXNYH FAZ SLIYANIYA. zAMETIM, CHTO ESLI IMEYUTSYA 
SOBSTVENNYE KOMANDY, TO DOLZHNO BYTX PO KRAJNEJ MERE DVA PROHODA PO FAJLU, 
DAZHE ESLI ON PERVONACHALXNO NAHODILSYA V PORYADKE. sOBSTVENNYE KOMANDY, 
IZMENYAYUSHCHIE RAZMER ZAPISEJ, MOGUT ZATRUDNITX SOVMESHCHENIE NEKOTORYH 
OPERACIJ VVODA/VYVODA V OSCILLIRUYUSHCHEJ SORTIROVKE.

gENERATORY SORTIROVKI TAKZHE ZABOTYATSYA O SISTEMNYH DETALYAH, TAKIH, KAK 
SOGLASHENIYA O METKAH LENT; ONI TAKZHE CHASTO OBESPECHIVAYUT PODSCHET 
KONTROLXNOJ SUMMY ILI INYE PROVERKI TOGO, CHTO NIKAKAYA CHASTX FAJLA NE 
PROPALA I NE IZMENILASX. iNOGDA IMEYUTSYA SREDSTVA DLYA OSTANOVKI SORTIROVKI 
V UDOBNYH MESTAH I VOZOBNOVLENIYA EE POZDNEE. sAMYE VYSOKOKACHESTVENNYE 
GENERATORY POZVOLYAYUT ZAPISYAM IMETX DINAMICHESKI MENYAYUSHCHIESYA DLINY [SM. 
D.~J.~Waks, {\sl CACM,\/} {\bf 6} (1963), 267--272].

\section *sLIYANIE S MENXSHIM CHISLOM BUFEROV. mY VIDELI, CHTO $2P+2$~BUFEROV 
DOSTATOCHNO DLYA PODDERZHANIYA BYSTROGO DVIZHENIYA LENT V TECHENIE 
$P\hbox{-PUTEVOGO}$ SLIYANIYA. v ZAVERSHENIE |TOGO PUNKTA PROVEDEM 
MATEMATICHESKIJ ANALIZ VREMENI SLIYANIYA V TOM SLUCHAE, KOGDA IMEETSYA MENXSHE 
$2P+2$~BUFEROV.

oCHEVIDNO, CHTO ZHELATELXNY DVA BUFERA VYVODA, TAK KAK MY SMOZHEM ZAPISYVATX 
IZ ODNOGO BUFERA, OBRAZUYA V |TO ZHE VREMYA SLEDUYUSHCHIJ BLOK VYVODA V DRUGOM. 
pO|TOMU MY MOZHEM VOOBSHCHE NE RASSMATRIVATX VOPROS VYVODA I ZANYATXSYA TOLXKO 
VVODOM.

dOPUSTIM, IMEETSYA $P+Q$~BUFEROV VVODA, GDE $1\le Q\le P$. vOSPOLXZUEMSYA 
DLYA OPISANIYA NASHEJ SITUACII MODELXYU, PREDLOZHENNOJ l.~dZH.~vUDRAMOM [{\sl 
IBM Systems J.,\/} {\bf 9} (1970), 118--144]. chTENIE ODNOGO BLOKA LENTY 
ZANIMAET ODNU EDINICU VREMENI. iMEETSYA VEROYATNOSTX~$p_0$ TOGO, CHTO V 
TECHENIE |TOGO VREMENI NI ODIN IZ BUFEROV VVODA NE STANET PUSTYM, $p_1$---CHTO 
ODIN BUFER STANET PUSTYM, $p{\ge 2}$---CHTO DVA ILI BOLXSHE BUFEROV STANUT 
%%407
PUSTYMI I~T.~D. pO ZAVERSHENII CHTENIYA LENTY MY OKAZYVAEMSYA V ODNOM 
IZ $Q+1$~SOSTOYANIJ:

\medskip
{\sl sOSTOYANIE~$0$:\/} $Q$~BUFEROV  PUSTY. mY NACHINAEM CHITATX 
BLOK PODHODYASHCHEGO FAJLA V ODIN IZ NIH, ISPOLXZUYA METOD PROGNOZIROVANIYA, 
OPISANNYJ RANEE V |TOM PUNKTE. chEREZ ODNU EDINICU VREMENI MY PEREHODIM V 
SOSTOYANIE~$1$ S VEROYATNOSTXYU~$p_0$, V PROTIVNOM SLUCHAE MY OSTAEMSYA V 
SOSTOYANII~$0$.

{\sl sOSTOYANIE~$1$:\/} $Q-1$~BUFEROV PUSTY. mY NACHINAEM CHITATX V ODIN IZ 
NIH, PREDSKAZYVAYA PODHODYASHCHIJ FAJL. chEREZ ODNU EDINICU VREMENI MY PEREHODIM 
V SOSTOYANIE~$2$ S VEROYATNOSTXYU~$p_0$, V SOSTOYANIE~$1$ S VEROYATNOSTXYU~$p_1$ 
I V SOSTOYANIE~$0$ S VEROYATNOSTXYU~$p_{\ge2}$.

$\vdots$

{\sl sOSTOYANIE~$Q-1$:\/} ODIN BUFER PUST. mY NACHINAEM CHITATX V NEGO, 
PREDSKAZYVAYA PODHODYASHCHIJ FAJL. chEREZ ODNU EDINICU VREMENI MY PEREHODIM V 
SOSTOYANIE~$Q$ S VEROYATNOSTXYU~$p_0$, V SOSTOYANIE~$Q-1$ S 
VEROYATNOSTXYU~$p_1$,~\dots, V SOSTOYANIE~$1$ S VEROYATNOSTXYU~$P_{Q-1}$, I V 
SOSTOYANIE~$0$ S VEROYATNOSTXYU~$p_{\ge Q}$.

{\sl sOSTOYANIE~$Q$:\/} VSE BUFERY ZAPOLNENY. chTENIE LENT OSTANAVLIVAETSYA 
V SREDNEM NA $\mu$~EDINIC VREMENI, I ZATEM MY PEREHODIM V SOSTOYANIE~$1$.
\medskip

mY NACHINAEM S SOSTOYANIYA~$0$. eTA MODELX SITUACII SOOTVETSTVUET 
MARKOVSKOMU PROCESSU (SM.~UPR.~2.3.4.2-26), KOTORYJ MOZHNO PROANALIZIROVATX 
S POMOSHCHXYU PROIZVODYASHCHIH FUNKCIJ SLEDUYUSHCHIM INTERESNYM SPOSOBOM. pUSTX 
$z$---PROIZVOLXNYJ PARAMETR, I PREDPOLOZHIM, CHTO KAZHDYJ RAZ, KOGDA MY 
RESHILI CHITATX S LENTY, DELAEM |TO S VEROYATNOSTXYU~$z$, A S 
VEROYATNOSTXYU~$1-z$ ZAVERSHAEM ALGORITM. pUSTX $g_Q(z)=\sum_{n\ge0} 
a_n^{(Q)}z^n(1-z)$ BUDET SREDNIM CHISLOM POYAVLENIJ V |TOM PROCESSE 
SOSTOYANIYA~$Q$; OTSYUDA SLEDUET, CHTO  $a_n^{(Q)}$---|TO SREDNEE CHISLO 
POYAVLENIJ SOSTOYANIYA~$Q$, ESLI BYLO PROCHITANO ROVNO $n$~BLOKOV. tOGDA 
$n+a_n\mu$---SREDNEE SUMMARNOE VREMYA, ZATRACHENNOE NA VVOD I VYCHISLENIYA. eSLI 
BY IMELOSX POLNOE SOVMESHCHENIE, KAK V ALGORITME S $(2P+2)$~BUFERAMI, 
TO SUMMARNOE VREMYA VKLYUCHALO BY TOLXKO $n$~EDINIC, TAK CHTO 
$a_n\mu$~PREDSTAVLYAET VREMYA ZADERZHKI CHTENIYA.

pUSTX $A_{ij}$---VEROYATNOSTX TOGO, CHTO MY PEREHODIM IZ SOSTOYANIYA~$i$ V 
SOSTOYANIE~$j$ V |TOM PROCESSE PRI~$0\le i$, $j\le Q+1$, GDE $Q+1$---NOVOE 
SOSTOYANIE "OSTANOVKI". nAPRIMER, DLYA $Q=1$, $2$, $3$ MATRICY~$A$ BUDUT 
SLEDUYUSHCHIMI:
%%407
$$
\eqalign{
Q&=1:\pmatrix{
p_{\ge1}z & p_0z & 1-z\cr
1 & 0 & 0\cr
0 & 0 & 0\cr
},\cr
Q&=2:\pmatrix{
p_{\ge1}z & p_0z & 0 & 1-z\cr
p_{\ge2}z & p_1z & p_0z& 1-z\cr
0 & 1 & 0 & 0 \cr
0 & 0 & 0 & 0\cr
},\cr
Q&=3:\pmatrix{
p_{\ge1}z & p_0z & 0 & 0 & 1-z\cr
p_{\ge2}z & p_1z & p_0z& 0 & 1-z\cr
p_{\ge3}z & p_2z & p_1z& p_0z & 1-z\cr
0 & 0 & 1 & 0 & 0\cr
0 & 0 & 0& 0 & 0 \cr
}.\cr
}
$$
iZ UPR.~2.3.4.2-26b IMEEM, CHTO 
$g_Q(z) =\hbox{ ALGEBRAICHESKOE DOPOLNENIE $Q_0$}  (I-A)/\det (I-A)$. tAK, 
NAPRIMER, ESLI $Q=1$, IMEEM
$$
\eqalign{
g_1(z)&=\det\pmatrix{
0 & -p_0z & z-1\cr
1 & 0 & 0 \cr
0 & 0 & 1\cr
}/
\det\pmatrix{
1-p_{\ge1}z & -p_0z & z-1\cr
-1 & 1 & 0\cr
0& 0 & 1\cr
}=\cr
&={p_0z\over 1-p_1z-p_0z}={p_0z\over1-z}=\sum_{n\ge0} np_0z^n(1-z),\cr
}
$$
TAK CHTO $a_n^{(1)}=np_0$. eTO, KONECHNO, OCHEVIDNO ZARANEE, TAK KAK 
PRI $Q=1$ ZADACHA OCHENX PROSTA. aNALOGICHNOE VYCHISLENIE DLYA 
$Q=2$ (SM.~UPR.~14) DAET MENEE OCHEVIDNUYU FORMULU:
$$
a_n^{(2)}={p_0^2n\over 1-p_1}-{p_0^2(1-p_1^n)\over(1-p_1)^2}.
\eqno(10)
$$
v OBSHCHEM SLUCHAE MOZHNO POKAZATX, CHTO $a_n^{(Q)}$ IMEET 
VID~$\alpha^{(Q)}n+O(1)$ PRI $n\to\infty$, GDE KONSTANTU~$\alpha^{(Q)}$ 
NE SLISHKOM TRUDNO VYCHISLITX. (sM. UPR.~15.) kAK OKAZYVAETSYA, $\alpha^{(3)}=p_0^3/((1-p_1)^2-p_0p_2)$.

iSHODYA IZ PRIRODY SLIYANIYA, DOVOLXNO RAZUMNO PREDPOLOZHITX, CHTO $\mu=1/P$ I 
CHTO VEROYATNOSTI~$p_k$ SOOTVETSTVUYUT BINOMIALXNOMU RASPREDELENIYU
$$
p_k=\perm{P}{k}\perm{1}{P}^k{\left({P-1\over P}\right)\hbox to 0pt{.\hss}}^{P-k}
$$
nAPRIMER, ESLI $P=5$, TO $p_0= .32768$, $p_1=.4096$, $p_2= .2048$, 
$p_3=.0512$, $p_4=.0064$ I~$p_5=.00032$; SLEDOVATELXNO, $\alpha^{(1)}=0.328$, 
$\alpha^{(2)}=0.182$ I~$\alpha^{(3)}=0.127$. dRUGIMI SLOVAMI, ESLI MY 
ISPOLXZUEM $5+3$~VVODNYH BUFEROV VMESTO~$5+5$, TO MOZHNO OZHIDATX 
DOPOLNITELXNOGO VREMENI  ZADERZHKI CHTENIYA PORYADKA~$0.127/5\approx 2.5\%$.

%% 409

kONECHNO, |TA MODELX---TOLXKO OCHENX GRUBOE PRIBLIZHENIE. mY ZNAEM, CHTO PRI 
$Q=P$ VOOBSHCHE NET VREMENI ZADERZHKI, NO ESLI SUDITX PO MODELI, TO ESTX. 
dOPOLNITELXNOE VREMYA ZADERZHKI CHTENIYA DLYA MENXSHIH~$Q$ POCHTI TOCHNO 
URAVNOVESHIVAET VYIGRYSH V NAKLADNYH RASHODAH, POLUCHAEMYJ OT ISPOLXZOVANIYA 
BOLEE KRUPNYH BLOKOV, TAK CHTO PROSTAYA SHEMA S $Q=P$ KAZHETSYA OPRAVDANNOJ.
\excercises

\ex[13] vYVEDITE FORMULU DLYA TOCHNOGO CHISLA LITER NA LENTE, ESLI KAZHDYJ 
BLOK SODERZHIT $n$~LITER. sCHITAJTE, CHTO LENTA MOGLA BY VMESTITX 
ROVNO 23000000 LITER, ESLI BY NE BYLO MEZHBLOCHNYH PROMEZHUTKOV.

\ex[15] oB�YASNITE, POCHEMU PERVYJ BUFER FAJLA~$2$ V STROKE~$6$ RIS.~84 
SOVSEM PUST.

\ex[20] bUDET LI ALGORITM~F RABOTATX DOLZHNYM OBRAZOM, ESLI VMESTO 
$2P$~BUFEROV VVODA IMEETSYA TOLXKO $2P-1$? eSLI DA, DOKAZHITE |TO, ESLI 
NET--- PRIVEDITE PRIMER, KOGDA ALGORITM TERPIT NEUDACHU.

\ex[20] kAK IZMENITX ALGORITM~F, CHTOBY ON RABOTAL TAKZHE I PRI~$P=1$?

\rex[21] eSLI V RAZLICHNYH FAJLAH IMEYUTSYA RAVNYE KLYUCHI, NEOBHODIMO V 
PROCESSE PROGNOZIROVANIYA DEJSTVOVATX OCHENX AKKURATNO. oB�YASNITE, POCHEMU, I 
POKAZHITE, KAK IZBEZHATX TRUDNOSTEJ, ESLI BOLEE STROGO OPREDELITX 
OPERACII SLIYANIYA I PROGNOZIROVANIYA V ALGORITME~F.

\ex[22] kAKIE IZMENENIYA SLEDUET SDELATX V ALGORITME~5.4.3s, CHTOBY 
PREOBRAZOVATX EGO V ALGORITM KASKADNOGO SLIYANIYA \emph{S SOVMESHCHENIEM 
PEREMOTKI} NA  $T+1$~LENTAH?

\rex [26] nACHALXNOE RASPREDELENIE V PRIMERE~7 SHEMY~a POROZHDAET
$$
(A_1D_1)^{11}\quad D_1(A_1D_1)^{10}\quad D_1(A_1D_1)^9\quad D_1(A_1D_1)^7
$$
NA LENTAH~1--4, GDE $(A_1D_1)^7$ OZNACHAET 
$A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1$. pOKAZHITE, KAK VSTAVITX 
DOPOLNITELXNYE OTREZKI~$A_0$ I~$D_0$ NAILUCHSHIM IZ VOZMOZHNYH SPOSOBOV (V 
TOM SMYSLE, CHTO OBSHCHEE CHISLO OBRABATYVAEMYH VO VREMYA SLIYANIYA NACHALXNYH 
OTREZKOV BUDET MINIMALXNYM), CHTOBY PRIVESTI RASPREDELENIE K
$$
A(DA)^{14}\quad  (DA)^{28}\quad  (DA)^{26}\quad  (DA)^{22}.
$$
[\emph{uKAZANIE.} chTOBY SOHRANITX CHETNOSTX, NEOBHODIMO VSTAVLYATX~$A_0$ 
I~$D_0$ V VIDE SOSEDNIH PAR. chISLA SLIYANIYA DLYA KAZHDOGO NACHALXNOGO OTREZKA 
MOGUT BYTX PODSCHITANY, KAK V UPR~5.4.4-5; ZDESX POYAVLYAETSYA NEKOTOROE 
UPROSHCHENIE, TAK KAK SOSEDNIE OTREZKI VSEGDA IMEYUT SOSEDNIE CHISLA SLIYANIYA.]

\ex[20] iZ SHEMY~a VIDNO, CHTO BOLXSHINSTVO SHEM NACHALXNOGO RASPREDELENIYA 
OTREZKOV (ZA ISKLYUCHENIEM NACHALXNOGO RASPREDELENIYA DLYA KASKADNOGO SLIYANIYA) 
IMEET TENDENCIYU POMESHCHATX POSLEDOVATELXNYE OTREZKI NA RAZLICHNYE LENTY. eSLI 
BY POSLEDOVATELXNYE OTREZKI POPALI NA ODNU LENTU, TO MY MOGLI BY 
S|KONOMITX STARTSTOPNOE VREMYA; MOZHNO LI PO|TOMU SCHITATX HOROSHEJ 
MYSLX IZMENITX ALGORITMY RASPREDELENIYA TAK, CHTOBY ONI REZHE PEREKLYUCHALI LENTY?

\rex[22] oCENITE, SKOLXKO VREMENI ZANYAL BY MNOGOFAZNYJ ALGORITM S OBRATNYM 
CHTENIEM IZ SHEMY~a, ESLI BY MY ISPOLXZOVALI DLYA SORTIROVKI VSE $T=6$ LENT, 
A NE $T=5$, KAK V PRIMERE~7. bYLO LI RAZUMNO IZBEGATX ISPOLXZOVANIYA 
VVODNOJ LENTY?

\ex[m23] iSPOLXZUYA ANALIZ, PROVEDENNYJ V P.~5.4.2 I~5.4.3, POKAZHITE, CHTO 
DLINA KAZHDOJ PEREMOTKI VO VREMYA STANDARTNOGO MNOGOFAZNOGO SLIYANIYA S SHESTXYU 
LENTAMI ILI KASKADNOGO SLIYANIYA REDKO PREVYSHAET 54\% FAJLA (ISKLYUCHAYA 
NACHALXNUYU I KONECHNUYU PEREMOTKI, KOTORYE OHVATYVAYUT VESX FAJL).

%%410
\ex[23] iZMENIV PODHODYASHCHIE |LEMENTY TABL.~1, OCENITE, SKOLXKO 
VREMENI ZANYALI BY PERVYE DEVYATX PRIMEROV SHEMY~a, ESLI BY MY IMELI 
DVUHSKOROSTIUYU PEREMOTKU (BYSTRUYU I MEDLENNUYU) sCHITAJTE, CHTO $p=1$, ESLI 
LENTA ZAPOLNENA MENXSHE CHEM NA ODNU CHETVERTX, A DLYA BOLEE ZAPOLNENNOJ 
LENTY VREMYA PEREMOTKI RAVNO PRIBLIZITELXNO PYATI SEKUNDAM PLYUS TO VREMYA, 
KOTOROE POLUCHILOSX BY PRI $\rho=1/5$ iZMENITE PRIMER~8 TAK, CHTOBY ON 
ISPOLXZOVAL KASKADNOE SLIYANIE S KOPIROVANIEM, POSKOLXKU PEREMETKA I 
PRYAMOE CHTENIE V |TOM SLUCHAE MEDLENNEE KOPIROVANIYA [\emph{uKAZANIE:} 
ISPOLXZUJTE REZULXTAT UPR. 10 ]

\ex[40] rASSMOTRIM RAZBIENIE SHESTI LENT NA TRI PARY LENT, GDE KAZHDAYA PARA 
IGRAET ROLX ODNOJ LENTY V MNOGOFAZNOM SLIYANII S~$T=3$ oDNA LENTA KAZHDOJ 
PARY BUDET SODERZHATX BLOKI~$1$, $3$, $5$,~\dots, A DRUGAYA---BLOKI~$2$, $4$, 
$6$,~\dots, TAKIM SPOSOBOM MY, PO SUSHCHESTVU, DOBIVAEMSYA TOGO, CHTOBY VO VSE 
VREMYA SLIYANIYA DVE VVODNYE I DVE VYVODNYE LENTY OSTAVALISX AKTIVNYMI, 
PRICHEM |FFEKTIVNAYA SKOROSTX SLIYANIYA UDVAIVAETSYA

\item{(a)} nAJDITE PODHODYASHCHIJ SPOSOB RASPROSTRANITX ALGORITM~F NA |TOT SLUCHAJ.

\item{(b)} oCENITE OBSHCHEE VREMYA VYPOLNENIYA, KOTOROE POLUCHILOSX BY, ESLI BY 
|TOT METOD BYL ISPOLXZOVAN DLYA SORTIROVKI 100000~ZAPISEJ PO 100~LITER, 
RASSMOTREV SLUCHAJ KAK PRYAMOGO, TAK I OBRATNOGO CHTENIYA.

\ex[20] mOZHET LI OSCILLIRUYUSHCHAYA SORTIROVKA S PYATXYU LENTAMI, V TOM VIDE KAK 
ONA OPREDELENA V ALGORITME 5.4.5v, ISPOLXZOVATXSYA DLYA SORTIROVKI CHETYREH 
POLNYH BOBIN ISHODNYH DANNYH DO MOMENTA OKONCHATELXNOGO SLIYANIYA?

\ex[m19] vYVEDITE (10).

\ex[vm29] dOKAZHITE, CHTO $g_Q(z)=h_Q(z)/(1-z)$, GDE $h_Q(z)$~YAVLYAETSYA 
RACIONALXNOJ FUNKCIEJ~$z$,  NE IMEYUSHCHEJ OSOBENNOSTEJ VNUTRI EDINICHNOGO KRUGA;
SLEDOVATELXNO, $a_n^{(Q)}=h_Q(1)n+O(1)$ PRI $n\to\infty$. v CHASTNOSTI, 
POKAZHITE, CHTO
$$
h_3(1)=\det\pmatrix{
0 & -p_0 & 0 & 0 \cr
0 & 1-p_1 & -p_0 & 0 \cr
0 & -p_2 & 1-p_1 & -p_0 \cr
1 & 0 & 0 & 0 \cr
}
/\det\pmatrix{
1 & -p_0 & 0 & 0 \cr
1 & 1-p_1 & -p_0 & 0 \cr
1 & -p_2 & 1-p_1 & -p_0\cr
0 & 0 & -1 & 1 \cr
}.
$$
\ex[M46] pROANALIZIRUJTE SLIYANIE S $P+Q$~BUFERAMI BOLEE TSHCHATELXNO, CHEM |TO 
BYLO SDELANO V TEKSTE, ISPOLXZUYA BOLEE TOCHNUYU MODELX.

\ex[41] pROVEDITE DETALXNOE IZUCHENIE ZADACHI SORTIROVKI 100000~ZAPISEJ YAO 
100~LITER, NARISUJTE SHEMY, PODOBNYE SHEME~a, V PREDPOLOZHENII, 
CHTO IMEETSYA~3, 4 ILI~5 LENT

\subsubchap{*vNESHNYAYA PORAZRYADNAYA SORTIROVKA} %5.4.7
v PREDYDUSHCHIH PUNKTAH MY RASSMOTRELI PROCESS LENTOCHNOJ   SORTIROVKI 
SLIYANIEM; NO SUSHCHESTVUET I DRUGOJ SPOSOB SORTIROVKI NA LENTAH, OSNOVANNYJ 
NA PRINCIPE PORAZRYADNOJ SORTIROVKI, ISPOLXZUEMOJ V MEHANICHESKIH 
SORTIROVALXNYH MASHINAH DLYA PERFOKART (SR. S P.~5.2.5). eTOT METOD INOGDA 
NAZYVAYUT RASPREDELYAYUSHCHEJ SORTIROVKOJ, POKOLONNOJ SORTIROVKOJ, 
KARMANNOJ SORTIROVKOJ, CIFROVOJ SORTIROVKOJ, SORTIROVKOJ RAZDELENIEM I T. 
D. oN, KAK OKAZYVAETSYA, PO SUSHCHESTVU, \emph{PROTIVOPOLOZHEN} SLIYANIYU!

pREDPOLOZHIM, NAPRIMER, CHTO V NASHEM RASPORYAZHENII IMEYUTSYA CHETYRE LENTY, A 
KLYUCHEJ MOZHET BYTX TOLXKO VOSEMX: $0$, $1$, $2$, $3$, 
%%411
$4$, $5$, $6$, $7$. eSLI ISHODNYE DANNYE NAHODYATSYA NA LENTE~$T1$, 
TO NACHNEM S PEREPISI VSEH CHETNYH KLYUCHEJ NA~$T3$ I VSEH NECHETNYH NA~$T4$:
\ctable{
\hfill#&&\bskip\hfill$#$\hfill\bskip\cr
 & T1 & T2 & T3 & T4 \cr
dANO    & \{0, 1, 2, 3, 4, 5, 6, 7\} & - & - & - \cr
pROHOD 1& - & - & \{0, 2, 4, 6\} & \{1, 3, 5, 7\}\cr
\noalign{
\noindent tEPERX PEREMATYVAEM LENTY I CHITAEM~$T3$, A ZATEM ~$T4$, POMESHCHAYA 
$\{0, 1, 4, 5\}$ NA~$T1$ I~$\{2,  3,  6,  7\}$ NA~$T2$:
}
pROHOD 2. &  \{0,4\} \{1,5\}  &     \{2,6\} \{3,7\} & - &- \cr
\noalign{
\noindent(sTROKA~$\{0, 4\}\{1, 5\}$ OBOZNACHAET FAJL, SODERZHASHCHIJ ZAPISI 
TOLXKO S KLYUCHAMI~$0$ I~$4$, ZA KOTORYMI SLEDUYUT ZAPISI TOLXKO S 
KLYUCHAMI~$1$ I~$5$. zAMETIM, CHTO~$T1$ TEPERX SODERZHIT TE KLYUCHI, SREDNIJ 
DVOICHNYJ RAZRYAD KOTORYH SODERZHIT~$0$.) pOSLE ESHCHE ODNOJ PEREMOTKI I 
RASPREDELENIYA KLYUCHEJ~$0$, $1$, $2$, $3$ NA~$T3$ I KLYUCHEJ~$4$, $5$, $6$, 
$7$ NA~$T4$ MY IMEEM
}
pROHOD~3 & - & & \{0\}\{1\}\{2\}\{3\} &  \{4\} \{5\} \{6\} \{7\} \cr
}
tEPERX KOPIROVANIE~$T4$ V KONEC~$T3$ ZAVERSHAET RABOTU. v OBSHCHEM SLUCHAE DLYA 
KLYUCHEJ V DIAPAZONE OT~$0$ DO~$2^k-1$ MOZHNO OTSORTIROVATX FAJL 
ANALOGICHNYM OBRAZOM, ISPOLXZOVAV $k$~PROHODOV, ZA KOTORYMI SLEDUET FAZA 
OKONCHATELXNOJ "SBORKI", KOPIRUYUSHCHAYA PRIMERNO POLOVINU DANNYH S ODNOJ LENTY 
NA DRUGUYU. iMEYA SHESTX LENT, MY MOZHEM ANALOGICHNYM OBRAZOM ISPOLXZOVATX 
PREDSTAVLENIYA PO OSNOVANIYU~$3$ DLYA SORTIROVKI KLYUCHEJ OT~$0$ DO~$3^k-1$ ZA $k$~PROHODOV.

iSPOLXZUYUTSYA TAKZHE METODY S CHASTICHNYMI PROHODAMI. pREDPOLOZHIM, NAPRIMER, 
CHTO DOPUSKAETSYA DESYATX KLYUCHEJ 
$\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$, I RASSMOTRIM SLEDUYUSHCHUYU PROCEDURU, 
PRINADLEZHASHCHUYU r.~l.~eSHENHERSTU [{\sl Theory of Switching,\/} {\bf 7} 
(Harvard Univ. Comp. Laboratory: May, 1954), I.1--I.76]:
\ctable{
\hfill#
&\bskip\hfill$#$\hfill\bskip
&\bskip\hfill$#$\hfill\bskip
&\bskip\hfill$#$\hfill\bskip
&\bskip\hfill$#$\hfill\bskip
&\bskip#\hfill\cr
 & T1 & T2 & T3 & T4 \cr
dANO    & \{0, 1,~\ldots, 9\} & - & - & - \cr
pROHOD~1.& - & \{0, 2, 4, 7\} & \{1, 5, 6\} & \{3, 8, 9\} & $1.0$~PROHOD \cr
pROHOD~2.& \{0\} & - & \{1, 5, 6\}\{2,7\} & \{3,8,9\}\{4\} &$0.4$~PROHODA\cr
pROHOD~3.& \{0\}\{1\}\{2\} & \{6\}\{7\} & - & \{3,8,9\}\{4\}\{5\}& $0.5$~PROHODA\cr
pROHOD~4. & \{0\}\{1\}\{2\}\{3\} & \{6\}\{7\}\{8\} & \{9\} &\{4\}\{5\}& $0.3$~PROHODA\cr
sBORKA & \{0\}\{1\}\{2\}\{3\}\{4\}\ldots\{9\} & & & & $0.6$~PROHODA\cr
& & & & & $\overline{\hbox{$2.8$ PROHODA}}$\cr
}

%%412

eSLI KAZHDOE ZNACHENIE KLYUCHA VSTRECHAETSYA PRIMERNO V ODNOJ DESYATOJ SLUCHAEV, 
TO |TA PROCEDURA DLYA SORTIROVKI DESYATI KLYUCHEJ ZATRACHIVAET TOLXKO 
$2.8$~PROHODA, V TO VREMYA KAK PERVYJ PRIMER TREBUET $3.5$~PROHODA DLYA 
SORTIROVKI VSEGO VOSXMI KLYUCHEJ. tAKIM OBRAZOM, MY VIDIM, CHTO ISKUSNAYA 
SHEMA RASPREDELENIYA MOZHET VYZVATX ZNACHITELXNOE RAZLICHIE DLYA 
PORAZRYADNOJ SORTIROVKI TOCHNO TAK ZHE, KAK DLYA SLIYANIYA.

sHEMY RASPREDELENIYA PREDYDUSHCHIH PRIMEROV PREDSTAVIM, KAK I OBYCHNO, 
DREVOVIDNYMI STRUKTURAMI:
\picture{RIS. NA STR. 412}
kRUGLYE VNUTRENNIE UZLY |TIH DEREVXEV ZANUMEROVANY~$1$, $2$, $3$,~\dots V 
SOOTVETSTVII S SHAGAMI PROCESSA~$1$, $2$, $3$,~\dots. iMENA LENT~$A$, $B$, 
$C$, $D$ (VMESTO $T1$, $T2$, $T3$, $T4$) POMESHCHENY RYADOM S REBRAMI DEREVA, 
CHTOBY UKAZATX, KUDA POPADAYUT ZAPISI. kVADRATNYE VNESHNIE UZLY IZOBRAZHAYUT 
CHASTI FAJLA, SODERZHASHCHIE TOLXKO ODIN KLYUCH, I |TOT KLYUCH IZOBRAZHEN ZHIRNYM 
SHRIFTOM POD SOOTVETSTVUYUSHCHIM UZLOM. rEBRA NAD KVADRATNYMI UZLAMI VSE 
POMECHENY IMENEM VYVODNOJ LENTY ($C$ V PERVOM PRIMERE, $A$ VO VTOROM).

tAKIM OBRAZOM, SHAG~3 PRIMERA~1 SOSTOIT IZ CHTENIYA S LENTY~$D$ I ZAPISI 
KLYUCHEJ~$1$ I~$5$ NA LENTU~$A$ I KLYUCHEJ~$3$ I~$7$ NA LENTU~$B$. nETRUDNO 
VIDETX, CHTO CHISLO VYPOLNYAEMYH PROHODOV RAVNO \emph{DLINE VNESHNEGO PUTI} 
DEREVA, DELENNOJ NA CHISLO VNESHNIH UZLOV, ESLI MY PRINIMAEM, CHTO VSE KLYUCHI 
RAVNOVEROYATNY.

v SILU POSLEDOVATELXNOJ PRIRODY LENTY I DISCIPLINY "PERVYM 
VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA", KOTOROJ PODCHINYAETSYA PRYAMOE CHTENIE, 
NELXZYA VZYATX ZA OSNOVU SHEMY RASPREDELENIYA \emph{LYUBOE} POMECHENNOE DEREVO. 
v DEREVE PRIMERA~1 DANNYE ZAPISYVAYUTSYA NA LENTU~$A$ NA SHAGE~2 I SHAGE~3; 
DANNYE, ZAPISANNYE V TECHENIE SHAGA~2, NEOBHODIMO ISPOLXZOVATX RANXSHE DANNYH,
 ZAPISANNYH V TECHENIE SHAGA~3. v OBSHCHEM SLUCHAE, ESLI MY ZAPISYVAEM NA 
LENTU V TECHENIE SHAGOV~$i$ I~$j$, GDE $i < j$, PERVYMI SLEDUET
%%413
ISPOLXZOVATX DANNYE, ZAPISANNYE V TECHENIE SHAGA~$i$; ESLI DEREVO 
SODERZHIT DVE VETVI VIDA
\picture{RIS. STR. 413}
TO DOLZHNO VYPOLNYATXSYA USLOVIE $k<l$. kROME TOGO, MY NE MOZHEM NICHEGO 
ZAPISYVATX NA LENTU~$A$ \emph{MEZHDU} SHAGAMI~$k$ I~$l$, POSKOLXKU MEZHDU 
CHTENIEM I ZAPISXYU NEOBHODIMA PEREMOTKA.

tE CHITATELI, KOTORYE PRORABOTALI UPRAZHNENIYA P.~5.4.4, NEMEDLENNO POJMUT, 
CHTO DOPUSTIMYE DEREVXYA DLYA PORAZRYADNOJ SORTIROVKI S PRYAMYM CHTENIEM NA 
$T$~LENTAH---|TO V TOCHNOSTI "SILXNYE $T\hbox{-fifo}$" DEREVXYA, OPISYVAYUSHCHIE 
SORTIROVKU \emph{SLIYANIEM} NA $T$~LENTAH S PRYAMYM CHTENIEM! (sM. 
UPR.~5.4.4-20.) eDINSTVENNOE RAZLICHIE ZAKLYUCHAETSYA V TOM, CHTO VSE VNESHNIE 
UZLY RASSMATRIVAEMYH ZDESX DEREVXEV POMECHENY ODNOJ I TOJ ZHE LENTOJ. mY 
MOGLI BY SNYATX |TO OGRANICHENIE, PREDPOLOZHIV, CHTO SUSHCHESTVUET 
OKONCHATELXNAYA FAZA "SBORKI", PERENOSYASHCHAYA VSE ZAPISI NA VYVODNUYU LENTU, ILI 
MOGLI BY DOBAVITX |TO OGRANICHENIE K PRAVILAM DLYA $T\hbox{-fifo}$ DEREVXEV, 
POTREBOVAV, CHTOBY NACHALXNYJ RASPREDELITELXNYJ PROHOD SORTIROVKI SLIYANIEM 
BYL YAVNO VYRAZHEN V SOOTVETSTVUYUSHCHEM DEREVE SLIYANIYA.

iNYMI SLOVAMI, \emph{KAZHDOJ SHEME SLIYANIYA SOOTVETSTVUET 
SHEMA RASPREDELENIYA I KAZHDOJ SHEME RASPREDELENIYA SOOTVETSTVUET SHEMA 
SLIYANIYA.} pO NEKOTOROM RAZMYSHLENII |TO STANOVITSYA PONYATNYM. rASSMOTRIM 
SORTIROVKU SLIYANIEM, DELAYUSHCHUYU VSE NAOBOROT, T.~E.~"RAZLIVAYUSHCHUYU" 
OKONCHATELXNYJ VYVODNOJ FAJL V PODFAJLY, KOTORYE "RAZLIVAYUTSYA" V DRUGIE, 
I~T.D.; NAKONEC, MY RAZOLXEM FAJL V $S$~OTREZKOV. pODOBNAYA SHEMA 
VOZMOZHNA S LENTAMI TOGDA I TOLXKO TOGDA, KOGDA VOZMOZHNA SOOTVETSTVUYUSHCHAYA 
SHEMA RASPREDELENIYA DLYA PORAZRYADNOJ SORTIROVKA $S$~KLYUCHEJ. eTA 
DVOJSTVENNOSTX SLIYANIYA I RASPREDELENIYA POCHTI TOCHNA;
ONA NE VYPOLNYAETSYA TOLXKO V ODNOM OTNOSHENII: VVODNAYA LENTA DOLZHNA 
SOHRANYATXSYA V RAZNYE MOMENTY VREMENI.

pRIMER S VOSEMXYU KLYUCHAMI, RASSMOTRENNYJ V NACHALE |TOGO PUNKTA, OCHEVIDNO, 
DVOJSTVEN SBALANSIROVANNOMU SLIYANIYU NA CHETYREH LENTAH. pRIMER S DESYATXYU 
KLYUCHAMI I CHASTICHNYMI PROHODAMI SOOTVETSTVUET SLEDUYUSHCHEJ SHEME SLIYANIYA 
DESYATI OTREZKOV (ESLI MY SKROEM FAZY KOPIROVANIYA---SHAGI 6--11 V DEREVE):
\ctable{
#\hfill&&\bskip\hfill$#$\hfill\bskip\cr
 & T1 & T2 & T3 & T4 \cr
nACHALXNOE RASPREDELENIE &   1^4 & 1^3 & 1^1 & 1^2 \cr
shAG DEREVA 5 & 1^3 & 1^2 & - & 1^2 3^1 \cr
%%414
shAG DEREVA 4 & 1^2 &  1^1 &  2^1 & 1^23^1 \cr
shAG DEREVA 3 & 1^1 & - &  2^13^1 & 1^13^1 \cr
shAG DEREVA 2 &  -  & 4^1 & 3^1 & 3^1 \cr
shAG DEREVA 1 &  10^1& - & - & - \cr
}
eSLI SRAVNITX EE S PORAZRYADNOJ SORTIROVKOJ, TO-VIDNO, CHTO OBA METODA IMEYUT,
 V SUSHCHNOSTI, ODNU I TU ZHE STRUKTURU, NO OBRATNY VO VREMENI I IMEYUT 
OBRATNOE RASPOLOZHENIE SODERZHIMOGO NA LENTAH: $1^23^1$ (DVA OTREZKA 
DLINY~1 KAZHDYJ, ZA KOTORYMI NAHODITSYA ODIN OTREZOK DLINY~3) 
SOOTVETSTVUET 
$\{3, 8, 9\}{4} {5}$ (DVA PODFAJLA, SODERZHASHCHIE KAZHDYJ PO 1~KLYUCHU, 
PERED KOTORYMI RASPOLOZHEN ODIN PODFAJL, SODERZHASHCHIJ 3~KLYUCHA).

dVIGAYASX V DRUGUYU STORONU, MY MOZHEM V PRINCIPE POSTROITX PORAZRYADNUYU 
SORTIROVKU, DVOJSTVENNUYU MNOGOFAZNOMU SLIYANIYU, KASKADNOMU SLIYANIYU I T. D. 
nAPRIMER, MNOGOFAZNOMU SLIYANIYU 21~OTREZKA NA TREH LENTAH, IZOBRAZHENNOMU V 
NACHALE P.~5.4.2, SOOTVETSTVUET SLEDUYUSHCHAYA INTERESNAYA PORAZRYADNAYA SORTIROVKA:
\ctable{
\sevenrm#\hfill&&\bskip\hfill$\scriptstyle#$\hfill\cr
 & T1 & T2 & T3 \cr
dANO & \{0, 1, \ldots, 20\} & - & - \cr
pROHOD 1& - & \{0, 2, 4, 5, 7, 9, 10, 12, 13, 15, 17, 18, 20\} & \{1, 3, 6,
 8, 11, 14, 16, 19\}\cr
pROHOD 2 & \{0, 5, 10, 13, 18\} & - & \{1, 3, 6, 8, 11, 14, 16, 19\}\{2, 4,
 7, 9, 12, 15, 17, 20\}\cr
pROHOD 3 & \{0, 5, 10, 13, 18\} \{1, 6, 11, 14, 19\} \{2, 7, 12, 15, 20\} 
& \{3, 8, 16\} \{4, 9, 17\} & - \cr
pROHOD 4 & - & \{3, 8, 16\}\{4, 9, 17\} \{5, 10, 18\}\{6, 11, 19\}\{7, 12, 
20\} & \{0, 13\}\{1, 14\}\{2,15\}\cr
pROHOD 5 & \{8\}\{9\}\{10\}\{11\}\{12\} & - & \{0, 13\}\{1,14\}\{2, 
15\}\{3,16\}\ldots\{7,20\}\cr
pROHOD 6 & \{8\} \{9\} \{10\} \{11\} \{12\} \{13\}\ldots\{20\} & \{0\} 
\{1\} \ldots \{7\} & - \cr
}
pRAVILO RASPREDELENIYA, SOGLASNO KOTOROMU KLYUCHI RASPOLAGAYUTSYA NA LENTAH NA 
KAZHDOM SHAGE, KAZHETSYA MAGICHESKIM, NO NA SAMOM DELE ONO IMEET PROSTUYU sVYAZX 
S SISTEMOJ SCHISLENIYA, ISPOLXZUYUSHCHEJ CHISLA fIBONACHCHI! (sM. UPR.~2.)

\section oBRATNOE CHTENIE. dVOJSTVENNOSTX PORAZRYADNOJ SORTIROVKI I SLIYANIYA 
PRIMENIMA TAKZHE I K ALGORITMAM, CHITAYUSHCHIM LENTU V OBRATNOM NAPRAVLENII. mY 
OPREDELILI "$T\hbox{-lifo}$ DEREVXYA" V P.~5.4.4, I NETRUDNO VIDETX, CHTO 
ONI PODHODYAT DLYA PORAZRYADNOJ SORTIROVKI V TOJ ZHE MERE, CHTO I DLYA 
SORTIROVKI SLIYANIEM.

pORAZRYADNAYA SORTIROVKA S OBRATNYM CHTENIEM BYLA FAKTICHESKI RASSMOTRENA 
dZHONOM mOCHLI ESHCHE V 1946~G. V ODNOJ IZ PERVYH OPUBLIKOVANNYH RABOT PO 
SORTIROVKE VOOBSHCHE (SM. \S~5.5);
mOCHLI NA SAMOM DELE DAL SLEDUYUSHCHUYU KONSTRUKCIYU:
\ctable{
#\hfill&&\bskip\hfill$#$\hfill\bskip\cr
 & T1 & T2 & T3 & T4\cr
dANO & - & \{0, 1, \ldots, 9\} & - & - \cr
pROHOD 1& \{4, 5\} & - & \{2, 3, 6, 7\} & \{0, 1, 8, 9\}\cr
pROHOD 2&\{4, 5\} \{2, 7\} & \{3, 6\} & - & \{0, 1, 8, 9\}\cr
pROHOD 3&\{4,5\} \{2, 7\} \{0,9\} & \{3, 6\} \{1,8\}& - & - \cr
pROHOD 4& \{4, 5\} \{2, 7\} & \{3, 6\} \{1, 8\} & \{9\} & \{0\}\cr
\hfill\dots \cr
pROHOD  8 & - & - & \{9\}\{8\}\{7\}\{6\}\{5\} & \{0\}\{1\}\{2\}\{3\}\{4\}\cr
oKONCHATELXNAYA SBORKA & - & - & \{0\} \{1\}\{2\}\{3\}\{4\}\{5\}\ldots\{9\}\cr
}
%%415
\bye