\input style

eTA SHEMA NE YAVLYAETSYA NAIBOLEE |FFEKTIVNOJ SREDI VSEH VOZMOZHNYH, NO ONA 
INTERESNA TEM, CHTO POKAZYVAET, CHTO METODY S CHASTICHNYMI PROHODAMI 
RASSMATRIVALISX DLYA PORAZRYADNOJ SORTIROVKI ESHCHE V 1946~G., HOTYA V 
LITERATURE PO SLIYANIYU ONI POYAVILISX LISHX OKOLO 1960~G.

eFFEKTIVNAYA KONSTRUKCIYA SHEM RASPREDELENIYA S OBRATNYM CHTENIEM BYLA 
PREDLOZHENA e.~bAJESOM 
[{\sl CACM\/}, {\bf 11} (1968), 491--493]. pUSTX DANO $P+1$ LENT I $S$ 
KLYUCHEJ; RAZDELITE KLYUCHI NA $P$ PODFAJLOV, KAZHDYJ IZ KOTORYH SODERZHIT 
$\lfloor S/P \rfloor$ ILI $\lceil S/P \rceil$ KLYUCHEJ, I PRIMENYAJTE |TU 
PROCEDURU REKURSIVNO K KAZHDOMU PODFAJLU. eSLI $S<2P$, TO ODIN PODFAJL 
DOLZHEN SOSTOYATX IZ EDINSTVENNOGO NAIMENXSHEGO KLYUCHA; EGO I SLEDUET ZAPISATX 
NA VYVODNUYU LENTU. (oBSHCHAYA KONSTRUKCIYA S PRYAMYM PORYADKOM r.~m.~kARPA, 
OPISANNAYA V KONCE P.~5.4.4, VKLYUCHAET |TOT METOD KAK CHASTNYJ SLUCHAJ.)

oBRATNOE CHTENIE NESKOLXKO USLOZHNYAET SLIYANIE, POSKOLXKU ONI OBRASHCHAET 
PORYADOK OTREZKOV. sOOTVETSTVUYUSHCHIJ |FFEKT IMEETSYA I V PORAZRYADNOJ 
SORTIROVKE. rEZULXTAT OKAZYVAETSYA USTOJCHIVYM ILI "ANTIUSTOJCHIVYM" V 
ZAVISIMOSTI OT TOGO, KAKOJ UROVENX DOSTIGNUT V DEREVE. pOSLE PORAZRYADNOJ 
SORTIROVKI S OBRATNYM CHTENIEM, KOGDA NEKOTORYE VNESHNIE UZLY NAHODYATSYA NA 
CHETNYH UROVNYAH, A NEKOTORYE---NA NECHETNYH, DLYA ODNIH KLYUCHEJ OTNOSITELXNYJ 
PORYADOK RAZLICHNYH ZAPISEJ S ODINAKOVYMI KLYUCHAMI BUDET \emph{SOVPADATX} S 
PERVONACHALXNYM PORYADKOM, NO DLYA DRUGIH ON BUDET \emph{PROTIVOPOLOZHEN} 
ISHODNOMU. (sR. S UPR.~6.)

\emph{oSCILLIRUYUSHCHAYA} SORTIROVKA SLIYANIEM TAKZHE IMEET SVOYU PARU V |TOJ 
DVOJSTVENNOSTI. v \emph{OSCILLIRUYUSHCHEJ PORAZRYADNOJ SORTIROVKE} MY 
PRODOLZHAEM RAZDELYATX KLYUCHI, POKA NE DOSTIGNEM POD- FAJLOV, SODERZHASHCHIH 
TOLXKO ODIN KLYUCH ILI DOSTATOCHNO MALYH, CHTOBY PODDAVATXSYA VNUTRENNEJ 
SORTIROVKE; TAKIE PODFAJLY SORTIRUYUTSYA I ZAPISYVAYUTSYA NA VYVODNUYU LENTU, 
ZATEM PROCESS RAZDELENIYA VOZOBNOVLYAETSYA. nAPRIMER, ESLI IMEYUTSYA TRI 
RABOCHIE LENTY I ODNA VYVODNAYA I ESLI KLYUCHI YAVLYAYUTSYA DVOICHNYMI CHISLAMI, 
MY MOZHEM NACHATX S TOGO, .CHTO POMESTIM KLYUCHI VIDA `$0x$' NA LENTU T1, A 
KLYUCHI `$1x$' NA LENTU T2. eSLI NA LENTE T1 OKAZHETSYA BOLXSHE ZAPISEJ, CHEM 
EMKOSTX PAMYATI, TO VNOVX PROSMATRIVAEM EE I POMESHCHAET `$00x$' NA T2 I 
`$01x$' NA Tz. tEPERX, ESLI PODFAJL `$00x$' DOSTATOCHNO KOROTKIJ, 
PROIZVODIM VNUTRENNYUYU SORTIROVKU EGO I VYVODIM REZULXTAT, A ZATEM 
NACHINAEM OBRABOTKU PODFAJLA `$01x$'. pODOBNYJ METOD BYL 
NAZVAN e.~X.~fR|NDOM "KASKADNOJ PSEVDOPORAZRYADNOJ SORTIROVKOJ" [{\sl 
JACM\/}, {\bf 3} (1956), 157--159]; BOLEE PODROBNO EGO 
RAZRABOTALI X.~n|GLER [{\sl JACM\/}, {\bf 6} (1959), 459--468], KOTORYJ 
DAL EMU KRASOCHNOE IMYA "METOD DVUGLAVOGO ZMIYA", I k. X. gODETT 
[{\sl IBM Tech. Disclosure Bull.\/}, {\bf 12} (April, 1970), 1849--1853].

%% 416
\qsection pREVOSHODIT LI PORAZRYADNAYA SORTIROVKA SLIYANIE? oDNIM VAZHNYM 
SLEDSTVIEM PRINCIPA DVOJSTVENNOSTI YAVLYAETSYA TO, CHTO 
\emph{PORAZRYADNAYA SORTIROVKA OBYCHNO HUZHE SORTIROVKI SLIYANIEM}. 
eTO SVYAZANO S TEM, CHTO METOD 
VYBORA S ZAMESHCHENIEM DAET SORTIROVKE SLIYANIEM OPREDELENNOE PREIMUSHCHESTVO: 
NET OCHEVIDNOGO PUTI TAK POSTROITX PORAZRYADNUYU SORTIROVKU, CHTOBY MOZHNO BYLO 
ISPOLXZOVATX VNUTRENNIE SORTIROVKI, VKLYUCHAYUSHCHIE BOLEE ODNOJ EMKOSTI 
PAMYATI ZA ODIN RAZ. nA SAMOM DELE OSCILLIRUYUSHCHAYA PORAZRYADNAYA SORTIROVKA 
CHASTO BUDET POROZHDATX PODFAJLY, NESKOLXKO MENXSHIE EMKOSTI PAMYATI, TAK 
CHTO EE SHEMA RASPREDELENIYA SOOTVETSTVUET DEREVU SO ZNACHITELXNO BOLXSHIM 
CHISLOM VNESHNIH UZLOV, CHEM BYLO BY PRI ISPOLXZOVANII SLIYANIYA I VYBORA S 
ZAMESHCHENIEM. sOOTVETSTVENNO VOZRASTAET DLINA VNESHNEGO PUTI DEREVA (T. E.
 VREMYA SORTIROVKI). (sM. UPR. 5.3.1--33.)

dLYA VNESHNEJ PORAZRYADNOJ SORTIROVKI SUSHCHESTVUET, ODNAKO, ODNO VAZHNOE 
PRIMENENIE. pREDPOLOZHIM, NAPRIMER, CHTO IMEETSYA FAJL, SODERZHASHCHIJ FAMILII 
VSEH SOTRUDNIKOV BOLXSHOGO PREDPRIYATIYA V ALFAVITNOM PORYADKE; PREDPRIYATIE 
SOSTOIT IZ 10 OTDELENIJ, I TREBUETSYA OTSORTIROVATX |TOT FAJL PO 
OTDELENIYAM, \emph{SOHRANYAYA} ALFAVITNYJ PORYADOK SOTRUDNIKOV V KAZHDOM 
OTDELENII. eSLI FAJL DLINNYJ, TO MY IMEEM DELO IMENNOE TOJ SITUACIEJ, 
GDE SLEDUET PRIMENYATX STABILXNUYU PORAZRYADNUYU SORTIROVKU, TAK KAK CHISLO 
ZAPISEJ, PRINADLEZHASHCHIH KAZHDOMU IZ 10 OTDELENIJ, BUDET, VEROYATNO, BOLXSHE, 
CHEM CHISLO ZAPISEJ, KOTOROE BYLO BY V NACHALXNYH OTREZKAH, POLUCHENNYH 
VYBOROM S ZAMESHCHENIEM. vOOBSHCHE GOVORYA, ESLI DIAPAZON KLYUCHEJ TAK MAL, CHTO 
NABOR ZAPISEJ S ODINAKOVYMI KLYUCHAMI BOLEE CHEM VDVOE PREVYSIT 
OPERATIVNUYU PAMYATX, TO RAZUMNO ISPOLXZOVATX PORAZRYADNUYU SORTIROVKU.

mY VIDELI V P.~5.2.5, CHTO NA NEKOTORYH VYSOKOSKOROSTNYH evm 
\emph{VNUTRENNYAYA} PORAZRYADNAYA SORTIROVKA PREDPOCHTITELXNEE SLIYANIYA, 
POSKOLXKU "VNUTRENNIJ CIKL" PORAZRYADNOJ SORTIROVKI OBHODITSYA BEZ SLOZHNYH 
PEREHODOV. eSLI VNESHNYAYA PAMYATX OCHENX BYSTRAYA, TO DLYA TAKIH MASHIN MOZHET 
OKAZATXSYA PROBLEMOJ PROVODITX SLIYANIE DANNYH S TAKOJ SKOROSTXYU, 
CHTOBY USPETX ZA OBORUDOVANIEM VVODA/VYVODA. pO|TOMU V PODOBNOJ SITUACII 
PORAZRYADNAYA SORTIROVKA, VOZMOZHNO, LUCHSHE SLIYANIYA, OSOBENNO ESLI IZVESTNO, 
CHTO KLYUCHI RAVNOMERNO RASPREDELENY.

\excercises
\ex[20] bLIZHE K NACHALU P. 5.4 BYLO OPREDELENO OBSHCHEE 
SBALANSIROVANNOE SLIYANIE NA $T$ LENTAH S PARAMETROM $P$, $1 \le P < T$. 
pOKAZHITE, CHTO ONO SOOTVETSTVUET PORAZRYADNOJ SORTIROVKE, ISPOLXZUYUSHCHEJ 
SISTEMU SCHISLENIYA SO SMESHANNYM OSNOVANIEM.

\ex[m28] v TEKSTE SHEMATICHESKI PREDSTAVLENA MNOGOFAZNAYA 
PORAZRYADNAYA SORTIROVKA 21 KLYUCHA! oBOBSHCHITE EE NA SLUCHAJ $F_n$ KLYUCHEJ; 
OB�YASNITE, KAKIE KLYUCHI I NA KAKOJ LENTE OKAZYVAYUTSYA V KONCE KAZHDOJ FAZY. 
[{\sl uKAZANIE:\/}
%% 417
RASSMOTRITE SISTEMU SCHISLENIYA, ISPOLXZUYUSHCHUYU CHISLA fIBONACHCHI; 
UPR. 1.2.8-34.]

\ex[m40] rASPROSTRANITE REZULXTATY UPR.~2 NA MNOGOFAZNUYU PORAZRYADNUYU 
SORTIROVKU S CHETYRXMYA ILI BOLXSHIM KOLICHESTVOM LENT (SR. S UPR.~5.4.2--10).

\ex[m20] dOKAZHITE, CHTO SHEMA RASPREDELENIYA eSHENHERSTA SLUZHIT NAILUCHSHIM 
SPOSOBOM SORTIROVKI 10 KLYUCHEJ NA CHETYREH LENTAH BEZ OBRATNOGO CHTENIYA V TOM 
SMYSLE, CHTO SOOTVETSTVUYUSHCHEE DEREVO IMEET MINIMALXNUYU DLINU VNESHNEGO PUTI 
SREDI VSEH "SILXNYH 4-fifo DEREVXEV". (tAKIM OBRAZOM, |TO, PO SUSHCHESTVU, 
NAILUCHSHIJ METOD, ESLI NE UCHITYVATX VREMYA PEREMOTKI.)

\ex[15] nARISUJTE 4-lifo DEREVO, SOOTVETSTVUYUSHCHEE PORAZRYADNOJ 
SORTIROVKE mOCHLI S OBRATNYM CHTENIEM 10 KLYUCHEJ.

\rex[20] nEKOTORYJ FAJL SODERZHIT DVUHRAZRYADNYE KLYUCHI $00$, $01$, \dots, 
$99$. pOSLE VYPOLNENIYA PORAZRYADNOJ SORTIOVKI mOCHLI PO CIFRE EDINIC MY 
MOZHEM POVTORITX TU ZHE SHEMU PO CIFRE DESYATKOV, POMENYAV ROLYAMI LENTY 
$T2$ I $T4$. v KAKOM PORYADKE V KONCE KONCOV OKAZHUTSYA KLYUCHI NA $T2$?

\ex[21] pRIMENIM LI PRINCIP DVOJSTVENNOSTI TAKZHE I K FAJLAM NA 
NESKOLXKIH BOBINAH?

\subsubchap{sORTIROVKA S DVUMYA LENTAMI}
dLYA TOGO CHTOBY PRI VYPOLNENII SLIYANIYA NE BYLO CHREZMERNOGO DVIZHENIYA LENT,
 NEOBHODIMY TRI LENTY. iNTERESNO PODUMATX O TOM, KAK MOZHNO RAZUMNYM 
OBRAZOM VYPOLNITX VNESHNYUYU SORTIROVKU S ISPOLXZOVANIEM TOLXKO DVUH LENT.

v 1956~G. g.~b.~dEMUT PREDLOZHIL NEKIJ METOD, PREDSTAVLYAYUSHCHIJ SOBOJ 
KOMBINACIYU VYBORA S ZAMESHCHENIEM I SORTIROVKI METODOM PUZYRXKA. 
pREDPOLOZHIM, CHTO ISHODNYE DANNYE ZANIMAYUT LENTU $T1$, I NACHNEM S TOGO, 
CHTO PROCHITAEM V PAMYATX $P+1$ ZAPISEJ. tEPERX VYVEDEM ZAPISX S 
NAIMENXSHIM KLYUCHOM NA LENTU $T2$ I ZAMENIM EE SLEDUYUSHCHEJ ISHODNOJ ZAPISXYU. 
pRODOLZHAEM VYVODITX ZAPISI, KLYUCH KOTORYH V TEKUSHCHIJ MOMENT NAIMENXSHIJ V 
PAMYATI, SOHRANYAYA DEREVO VYBORA ILI PRIORITETNUYU OCHEREDX IZ $P+1$ |LEMENTOV.
 kOGDA VVOD NAKONEC ISCHERPAETSYA, V PAMYATI OKAZHUTSYA NAIBOLXSHIE $P$ 
KLYUCHEJ FAJLA; VYVEDEM IH V VOZRASTAYUSHCHEM PORYADKE. tEPERX PEREMOTAEM OBE 
LENTY I POVTORIM |TOT PROCESS, CHITAYA S $T2$ I ZAPISYVAYA NA $T1$; KAZHDYJ 
TAKOJ PROHOD POMESHCHAET ESHCHE PO KRAJNEJ MERE $P$ ZAPISEJ NA SVOI MESTA. v 
PROGRAMMU MOZHNO VSTROITX PROSTUYU PROVERKU DLYA OPREDELENIYA MOMENTA, KOGDA 
VESX FAJL STANET UPORYADOCHENNYM. pOTREBUETSYA NE BOLEE  
$\lceil(N-1)/P\rceil$  PROHODOV.

mINUTNOE RAZMYSHLENIE POKAZYVAET, CHTO KAZHDYJ PROHOD |TOJ PROCEDURY 
|KVIVALENTEN $P$ POSLEDOVATELXNYM PROHODAM SORTIROVKI METODOM PUZYRXKA 
(ALGORITM 5.2.2v)! eSLI |LEMENT IMEET $P$ ILI BOLEE INVERSIJ, TO PRI VVODE 
ON OKAZHETSYA MENXSHE VSEH |LEMENTOV V DEREVE I PO|TOMU BUDET NEMEDLENNO 
VYVEDEN (POTERYAV, TAKIM OBRAZOM, $P$ INVERSIJ). eSLI |LEMENT IMEET MENEE 
$P$ INVERSIJ, TO ON POPADAET V DEREVO VYBORA I BUDET VYVEDEN RANXSHE VSEH 
BOLXSHIH KLYUCHEJ (POTERYAV, TAKIM OBRAZOM,
%% 418
VSE SVOI INVERSII). eSLI $P=1$, TO PROISHODIT TO ZHE SAMOE, CHTO I V METODE 
PUZYRXKA, PO TEOREME 5.2.21.

oBSHCHEE CHISLO PROHODOV BUDET, SLEDOVATELXNO, RAVNO $\lceil I/P \rceil$, GDE 
$I$---MAKSIMALXNOE CHISLO INVERSIJ LYUBOGO |LEMENTA. pO TEORII, RAZVITOJ V 
P.~5.2.2, SREDNEE ZNACHENIE $I$ ESTX 
$N-\sqrt{\pi N/2}+(2/3) +O(1/\sqrt{N})$.

eSLI FAJL NE SLISHKOM SILXNO PREVOSHODIT RAZMER OPERATIVNOJ PAMYATI ILI 
ESLI ON PERVONACHALXNO POCHTI UPORYADOCHEN, TO |TA SORTIROVKA METODOM PUZYRXKA 
$P$-GO PORYADKA BUDET DOVOLXNO BYSTROJ; V DEJSTVITELXNOSTI EE MOZHNO 
PREDPOCHESTX DAZHE V TOM SLUCHAE, KOGDA IMEYUTSYA DOPOLNITELXNYE 
LENTOPROTYAZHNYE USTROJSTVA, TAK KAK VESX PROCESS SORTIROVKI MOZHET 
ZAKONCHITXSYA RANXSHE, CHEM OPERATOR USPEET USTANOVITX TRETXYU LENTU! s 
DRUGOJ STORONY, ONA BUDET RABOTATX VESXMA MEDLENNO NAD DOVOLXNO BOLXSHIMI 
FAJLAMI SO SLUCHAJNYM RASPOLOZHENIEM |LEMENTOV, TAK KAK VREMYA EE RABOTY 
PRIBLIZITELXNO PROPORCIONALXNO $N^2$.

pOSMOTRIM, KAK REALIZUETSYA |TOT METOD DLYA 100000 ZAPISEJ V PRIMERE IZ 
P.~5.4.6. nAM NUZHNO RAZUMNO VYBRATX $P$, CHTOBY UCHESTX MEZHBLOCHNYE 
PROMEZHUTKI PRI SOVMESHCHENII OPERACIJ CHTENIYA I ZAPISI S VYCHISLENIYAMI. tAK 
KAK V PRIMERE PREDPOLAGAETSYA, CHTO KAZHDAYA ZAPISX IMEET DLINU 100 LITER, 
A 100000 LITER ZAPOLNYAYUT PAMYATX, TO U NAS BUDET MESTO DLYA DVUH BUFEROV 
VVODA I DVUH BUFEROV VYVODA RAZMERA $B$, ESLI VYBRATX ZNACHENIYA $P$ I $B$, 
TAKIE, CHTO
$$
100 (P+1) +4B =100000.
\eqno(1)
$$
eSLI ISPOLXZOVATX OBOZNACHENIYA P.~5.4.6, TO PRIBLIZITELXNOE VREMYA RABOTY 
KAZHDOGO PROHODA VYRAZHAETSYA KAK
$$
NC\omega\tau(1+\rho), \qquad \omega=(B+\gamma)/B.
\eqno (2)
$$
pOSKOLXKU CHISLO PROHODOV OBRATNO PROPORCIONALXNO $P$, MY HOTIM VYBRATX 
TAKOE $B$, KRATNOE 100, KOTOROE MINIMIZIRUET VELICHINU $\omega/P$. 
eLEMENTARNYJ ANALIZ POKAZYVAET, CHTO MINIMUM
DOSTIGAETSYA, KOGDA $B$ RAVNO PRIBLIZITELXNO 
$\sqrt{24975\gamma}+\gamma^2-\gamma$. pO|TOMU MY VYBIRAEM $B=3000$, $P=879$.
 pOLOZHIV V PRIVEDENNYH VYSHE FORMULAH $N=100000$, POLUCHAEM, CHTO CHISLO 
PROHODOV $\lceil I/P\rceil$ BUDET .OKOLO 114, A. OCENKA OBSHCHEGO VREMENI 
RESHENIYA SOSTAVLYAET PRIMERNO $8.57$~CH (PREDPOLAGAYA DLYA UDOBSTVA, 
CHTO ISHODNYE DANNYE I OKONCHATELXNYJ VYVOD TAKZHE IMEYUT $B=3000$). zDESX 
PREDSTAVLEN SLUCHAJ, KOGDA DANNYE ZANIMAYUT OKOLO $0.44$ BOBINY; POLNAYA 
BOBINA POTREBOVALA BY PRIMERNO V PYATX RAZ BOLXSHE VREMENI. mOZHNO PROIZVESTI 
NEKOTORYE ULUCHSHENIYA, PREDUSMOTREV V ALGORITME PERIODICHESKIE PRERYVANIYA I 
PERESYLKU ZAPISEJ S NAIBOLXSHIMI KLYUCHAMI NA VSPOMOGATELXNUYU 
%% 419
LENTU, KOTORAYA ZATEM SNIMAETSYA, NESKOLXKU |TI ZAPISI PROSTO 
KOPIRUYUTSYA TUDA I OBRATNO POSLE TOGO, KAK ONI UZHE OKAZALISX NA SVOIH MESTAH.

\section pRIMENENIE BYSTROJ SORTIROVKI. eSHCHE ODNIM METODOM VNUTRENNEJ 
SORTIROVKI, KOTORYJ PROHODIT DANNYE POCHTI POSLEDOVATELXNO, YAVLYAETSYA 
OBMENNAYA SORTIROVKA S RAZDELENIEM ILI BYSTRAYA SORTIROVKA (ALGORITM 5.2.2Q) 
mOZHNO LI EE PRISPOSOBITX K DVUM LENTAM? [N. v; Yoash, {\sl CACM\/}, {\bf 
8} (1965), 649.]

nETRUDNO UVIDETX KAK MOZHNO SDELATX |TO, VOSPOLXZOVAVSHISX OBRATNYM CHTENIEM. 
pREDPOLOZHIM, CHTO DVE LENTY POMECHENY 0 I 1, I PREDSTAVIM, CHTO FAJL 
RASPOLAGAETSYA SLEDUYUSHCHIM OBRAZOM:
\picture{rASPOLOZHENIE FAJLA NA LENTE, STR. 419}
kAZHDAYA LENTA VYSTUPAET V KACHESTVE STEKA. dVE LENTY VMESTE, ISPOLXZUEMYE 
KAK PREDSTAVLENO ZDESX, DAYUT VOZMOZHNOSTX SCHITATX FAJL LINEJNYM SPISKOM, 
V KOTOROM MY MOZHEM PEREMESHCHATX TEKUSHCHUYU POZICIYU VLEVO ILI VPRAVO, KOPIRUYA 
|LEMENTY IZ ODNOGO STEKA V DRUGOJ. sLEDUYUSHCHIE REKURSIVNYE PODPROGRAMMY 
OPREDELYAYUT SOOTVETSTVUYUSHCHUYU PROCEDURU SORTIROVKI.

\itemize
\li \strong{SORT00} [OTSORTIROVATX VERHNIJ PODFAJL S LENTY $0$ I VERNUTX 
EGO NA LENTU $0$]. eSLI PODFAJL POMESHCHAETSYA V OPERATIVNUYU PAMYATX, TO 
PRIMENITX K NEMU VNUTRENNYUYU SORTIROVKU I ZATEM VERNUTX EGO NA LENTU. v 
PROTIVNOM SLUCHAE VYBRATX ODNU ZAPISX $R$ IZ PODFAJLA; PUSTX EE KLYUCHOM 
BUDET $K$. chITAYA LENTU $0$ V OBRATNOM NAPRAVLENII, KOPIROVATX VSE ZAPISI, 
KLYUCHI KOTORYH $>K$, POLUCHAYA TAKIM OBRAZOM NOVYJ "VERHNIJ" PODFAJL NA LENTE 
$1$. tEPERX, CHITAYA LENTU $0$ V PRYAMOM NAPRAVLENII, KOPIROVATX VSE ZAPISI 
S KLYUCHAMI, RAVNYMI $K$, NA LENTU $1$. zATEM, VNOVX CHITAYA LENTU $0$ V 
OBRATNOM NAPRAVLENII, KOPIROVATX VSE ZAPISI S KLYUCHAMI $<K$ NA LENTU 1. 
vYPOLNITX \strong{SORT10} NAD KLYUCHAMI $<K$, ZATEM SKOPIROVATX KLYUCHI, 
RAVNYE $K$, NA LENTU $0$ I, NAKONEC, VYPOLNIV \strong{SORT10} NAD KLYUCHAMI 
$>K$, ZAVERSHITX SORTIROVKU.

\li \strong{SORT01} [OTSORTIROVATX VERHNIJ PODFAJL S LENTY 0 I ZAPISATX 
EGO NA LENTU 1]. aNALOGICHNO \strong{SORt00}, NO POSLEDNEE OBRASHCHENIE K 
\strong{"SORT10"} ZAMENENO NA \strong{"SORT11"}, ZA KOTORYM 
SLEDUET KOPIROVANIE KLYUCHEJ  $\le K$ NA LENTU 1.

\li \strong{SORT10} [OTSORTIROVATX VERHNIJ PODFAJL S LENTY 1 I ZAPISATX 
EGO NA LENTU 0]. tAKAYA ZHE, KAK \strong{SORT01}, NO MENYAYUTSYA MESTAMI 0 I~1, 
A TAKZHE OPERATORY OTNOSHENIJ $<$ I~$>$.
%% 420
\li \strong{SORT11} [OTSORTIROVATX VERHNIJ PODFAJL S LENTY 1 I VERNUTX 
EGO NA LENTU 1]. tAKAYA ZHE, KAK \strong{SORT00}, NO MENYAYUTSYA MESTAMI 0 I 1, 
A TAKZHE OTNOSHENIYA $<$ I $>$. mOZHNO BEZ TRUDA SPRAVITXSYA S REKURSIVNOJ 
PRIRODOJ |TIH PROCEDUR, ZAPISYVAYA PODHODYASHCHUYU UPRAVLYAYUSHCHUYU INFORMACIYU NA LENTY.
\itemend

eSLI SCHITATX, CHTO DANNYE NAHODYATSYA V SLUCHAJNOM PORYADKE I VEROYATNOSTX 
RAVNYH KLYUCHEJ PRENEBREZHIMO MALA, TO MOZHNO OCENITX VREMYA RABOTY |TOGO 
ALGORITMA SLEDUYUSHCHIM OBRAZOM. pUSTX $M$---CHISLO ZAPISEJ, POMESHCHAYUSHCHIHSYA V 
OPERATIVNOJ PAMYATI. pUSTX $X_N$---SREDNEE CHISLO ZAPISEJ, CHITAEMYH VO VREMYA 
PRIMENENIYA \strong{SORT00} ILI \strong{SORT11} K PODFAJLU IZ $N$ ZAPISEJ,
 GDE $N > M$, I PUSTX $Y_N$---SOOTVETSTVUYUSHCHAYA VELICHINA DLYA 
\strong{SORT01} I~\strong{SORT10}. tOGDA IMEEM:
$$
\eqalign{
 X_N&=\cases{
  0, & ESLI $N\le M$,\cr
  3N+1+{1\over N}\sum_{0\le k<N}(Y_k+Y_{N-1-k}), & ESLI $N>M$,\cr
 }\cr
 Y_N&=\cases{
  0, & ESLI $N\le M$,\cr
  3N+2+{1\over N}\sum_{0\le k<N}(Y_k+X_{N-1-k}+k), & ESLI $N>M$.\cr
 }\cr
}
\eqno(3)
$$
rESHENIE |TIH REKURRENTNYH SOOTNOSHENIJ (SM. UPR. 2) POKAZYVAET, CHTO OBSHCHIJ 
OB�EM INFORMACII, CHITAEMOJ S LENTY V TECHENIE FAZ VNESHNEGO RAZDELENIYA, V 
SREDNEM RAVEN $6{2\over 3}N\ln N+O(N)$
PRI $N\to\infty$. mY TAKZHE ZNAEM IZ FORMULY (5.2.2--25), CHTO SREDNEE CHISLO 
FAZ VNUTRENNEJ SORTIROVKI BUDET RAVNO $2(N+1)/(M+2)-1$.

eSLI MY PRIMENIM |TOT ANALIZ K PRIMERU 100000 ZAPISEJ, RASSMOTRENNOMU V 
P.~5.4.6, PRICHEM VOSPOLXZUEMSYA BUFERAMI PO 25000 LITER I BUDEM SCHITATX, 
CHTO VREMYA SORTIROVKI PODFAJLA IZ $n\le M=1000$ ZAPISEJ RAVNO 
$2nC\omega\tau$, TO POLUCHIM SREDNEE VREMYA SORTIROVKI, PRIBLIZITELXNO 
RAVNOE 103 MIN (VKLYUCHAYA, KAK V SHEME a, OKONCHATELXNUYU PEREMOTKU). iTAK, 
METOD BYSTROJ SORTIROVKI V SREDNEM NEPLOH; NO, KONECHNO, V 
\emph{NAIHUDSHEM} SLUCHAE ON UZHASEN I USTUPAET DAZHE METODU PUZYRXKA, 
OBSUZHDAVSHEMUSYA VYSHE.
\section pORAZRYADNAYA SORTIROVKA. oBMENNUYU PORAZRYADNUYU SORTIROVKU
(ALGORITM 5.2.2R) MOZHNO ANALOGICHNYM OBRAZOM PRISPOSOBITX DLYA SORTIROVKI S 
DVUMYA LENTAMI, TAK KAK ON OCHENX POHOZH NA BYSTRUYU SORTIROVKU. v KACHESTVE 
TRYUKA, KOTORYJ POZVOLIL
PRIMENITX OBA |TI METODA, ISPOLXZOVALASX IDEYA CHTENIYA FAJLA BOLEE CHEM ODIN 
RAZ---TO, CHEGO MY NIKOGDA NE DELALI V PREDYDUSHCHIH ALGORITMAH DLYA LENT.

%% 421

s POMOSHCHXYU TOGO ZHE TRYUKA MOZHNO OSUSHCHESTVITX OBYCHNUYU PORAZRYADNUYU 
SORTIROVKU NA DVUH LENTAH "SNACHALA-PO-MLADSHEJ-CIFRE". iMEYA ISHODNYE 
DANNYE NA $T1$, KOPIRUEM NA $T2$ VSE ZAPISI, KLYUCH KOTORYH V DVOICHNOJ 
SISTEME OKANCHIVAETSYA NA 0;
ZATEM POSLE PEREMOTKI $T1$ CHITAEM EE VNOVX, KOPIRUYA ZAPISI S KLYUCHAMI, 
OKANCHIVAYUSHCHIMISYA NA 1. tEPERX PEREMATYVAYUTSYA OBE LENTY I VYPOLNYAETSYA 
ANALOGICHNAYA PARA PROHODOV, NO S ZAMENOJ $T1$ NA $T2$ I ISPOLXZOVANIEM 
\emph{PREDPOSLEDNEJ} DVOICHNOJ CIFRY. v |TOT MOMENT $T1$ BUDET SODERZHATX 
VSE ZAPISI S KLYUCHAMI $(\ldots00)_2$, ZA KOTORYMI SLEDUYUT ZAPISI S KLYUCHAMI 
$(\ldots01)_2$, ZATEM $(\ldots10)_2$, ZATEM $(\ldots11)_2$. eSLI KLYUCHI 
IMEYUT RAZMER $b$ BITOV, NAM POTREBUETSYA, CHTOBY ZAVERSHITX SORTIROVKU, 
TOLXKO $2b$ PROHODOV PO VSEMU FAJLU.

pODOBNUYU PORAZRYADNUYU SORTIROVKU MOZHNO PRIMENYATX TOLXKO K \emph{STARSHIM} 
$b$ BITAM KLYUCHA DLYA NEKOTOROGO RAZUMNO VYBRANNOGO CHISLA $b$; TAKIM 
OBRAZOM, CHISLO INVERSIJ UMENXSHITSYA PRIMERNO V $2^b$ RAZ, ESLI KLYUCHI BYLI 
RAVNOMERNO RASPREDELENY; I TOGDA NESKOLXKO PROHODOV $P$-PUTEVOJ SORTIROVKI 
METODOM PUZYRXKA POZVOLYAT ZAVERSHITX RABOTU.

nOVYJ, NO NESKOLXKO BOLEE SLOZHNYJ PODHOD K RASPREDELYAYUSHCHEJ SORTIROVKE S 
DVUMYA LENTAMI PREDLOZHILI a. i. nIKITIN I l. i. shOLMOV [{\sl 
kIBERNETIKA\/}, {\bf 2}, 6 (1966), 79--84]. iMEYUTSYA SCHETCHIKI CHISLA KLYUCHEJ 
PO ODNOMU NA KAZHDUYU VOZMOZHNUYU KONFIGURACIYU STARSHIH BITOV, I NA OSNOVE 
|TIH SCHETCHIKOV STROYATSYA ISKUSSTVENNYE KLYUCHI $\kappa_1$, $\kappa_2$, 
\dots, $\kappa_M$ TAK, CHTOBY DLYA KAZHDOGO $i$ CHISLO DEJSTVITELXNYH KLYUCHEJ, 
LEZHASHCHIH MEZHDU $\kappa_i$ I $\kappa_{i+1}$, BYLO MEZHDU ZARANEE 
OPREDELENNYMI GRANICAMI $P_1$ I $P_2$. tAKIM OBRAZOM, $M$ LEZHIT MEZHDU 
$\lceil  N/P_1 \rceil$ I $\lceil N/P_1\rceil$. eSLI SCHETCHIKI STARSHIH BITOV 
NE DAYUT DOSTATOCHNOJ INFORMACII DLYA OPREDELENIYA TAKIH $\kappa_1$, 
$\kappa_2$, \dots, $\kappa_M$, TO DELAETSYA ESHCHE ODIN ILI NESKOLXKO 
PROHODOV DLYA PODSCHETA CHASTOTY KONFIGURACIJ MENEE ZNACHASHCHIH BITOV PRI 
NEKOTORYH KONFIGURACIYAH STARSHIH BITOV. pOSLE TOGO KAK TABLICA 
ISKUSSTVENNYH KLYUCHEJ POSTROENA, $2\lceil \log_2 M \rceil$  PROHODOV BUDET 
DOSTATOCHNO DLYA ZAVERSHENIYA SORTIROVKI. (eTOT METOD TREBUET PROSTRANSTVA 
PAMYATI, PROPORCIONALXNOGO $N$, I PO|TOMU NE MOZHET ISPOLXZOVATXSYA DLYA 
VNESHNEJ SORTIROVKI PRI $N\to\infty$. nA PRAKTIKE MY NE STANEM ISPOLXZOVATX 
|TOT METOD DLYA FAJLOV NA NESKOLXKIH BOBINAH, I, SLEDOVATELXNO, $M$ BUDET 
SRAVNITELXNO NEVELIKO, TAK CHTO TABLICA ISKUSSTVENNYH KLYUCHEJ LEGKO 
POMESTITSYA V PAMYATI.)

\section iMITACIYA DOPOLNITELXNYH LENT. f.~k.~hENNI I r.~e.~sTIRNZ IZOBRELI 
OBSHCHIJ METOD IMITACII $k$ LENT VSEGO NA DVUH LENTAH, PRICHEM TAKIM OBRAZOM, 
CHTO TREBUEMOE SUMMARNOE PEREMESHCHENIE LENTY VOZRASTAET VSEGO LISHX V $O(\log 
L)$ RAZ, GDE $L$---MAKSIMALXNOE RASSTOYANIE, KOTOROE NUZHNO PROJTI NA LYUBOJ ODNOJ
%% 422
LENTE [{\sl JACM\/}, {\bf 13} (1966), 533--546]. iH POSTROENIE V 
SLUCHAE SORTIROVKI MOZHNO SLEGKA UPROSTITX, CHTO I SDELANO V SLEDUYUSHCHEM 
METODE, PREDLOZHENNOM r.~m.~kARPOM.

bUDEM IMITIROVATX OBYCHNOE SBALANSIROVANNOE SLIYANIE NA CHETYREH LENTAH, 
ISPOLXZUYA DVE LENTY: $T1$ I $T2$. nA PERVOJ IZ NIH (T. E. NA $T1$) 
SODERZHIMOE IMITIRUEMYH LENT HRANITSYA TAKIM SPOSOBOM, KAK IZOBRAZHENO NA 
RIS.~86; PREDSTAVIM SEBE, CHTO DANNYE ZAPISANY NA CHETYREH DOROZHKAH PO ODNOJ 
DLYA KAZHDOJ IMITIRUEMOJ LENTY. (v DEJSTVITELXNOSTI LENTA NE IMEET TAKIH
\picture{rIS. 86. rAZBIVKA LENTY $T1$ V KONSTRUKCII hENNI I sTIRNZA}
DOROZHEK; MY MYSLIM BLOKI $1$, $5$, $9$, $13$, \dots  KAK DOROZHKU $1$,
 BLOKI $2$, $6$, $10$, $14$, \dots KAK DOROZHKU $2$ I T. D.) dRUGAYA LENTA 
($T2$) ISPOLXZUETSYA TOLXKO DLYA VSPOMOGATELXNOGO HRANENIYA, CHTOBY POMOCHX V 
VYPOLNENII PERESTANOVOK NA $T1$.

bLOKI NA KAZHDOJ DOROZHKE RAZDELYAYUTSYA NA \emph{ZONY}, 
SODERZHASHCHIE SOOTVETSTVENNO $1$, $2$, $4$, $8$, \dots, $2^k$, \dots BLOKOV. 
zONA $k$ NA KAZHDOJ DOROZHKE LIBO ZAPOLNENA TOCHNO $2^k$ BLOKAMI DANNYH, LIBO 
CELIKOM PUSTA. nAPRIMER, NA RIS.~86 NA DOROZHKE~$1$ DANNYE SODERZHATSYA V 
ZONAH~$1$ I~$3$; NA DOROZHKE $2$---V ZONAH $0$, $1$ I~$2$; NA DOROZHKE $3$---V 
ZONAH $0$ I~$2$; NA DOROZHKE 4---V ZONE~$1$, A VSE OSTALXNYE ZONY PUSTY.

pREDPOLOZHIM, CHTO MY SLIVAEM DANNYE S DOROZHEK $1$ I~$2$ NA DOROZHKU~$3$. v 
OPERATIVNOJ PAMYATI evm NAHODYATSYA DVA BUFERA, ISPOLXZUEMYE DVUHPUTEVYM 
SLIYANIEM DLYA VVODA, A TAKZHE TRETIJ BUFER---DLYA VYVODA. kOGDA BUFER VVODA DLYA 
DOROZHKI~$1$ STANET PUSTYM, MOZHNO ZAPOLNITX EGO SLEDUYUSHCHIM OBRAZOM: NAJTI 
PERVUYU NEPUSTUYU ZONU DOROZHKI~$1$, SKAZHEM ZONU $k$, I SKOPIROVATX PERVYJ EE 
BLOK V BUFER VVODA, ZATEM SKOPIROVATX OSTALXNYE $2^k-1$ BLOKOV DANNYH NA 
$T2$ I PEREMESTITX IH V ZONY 0, 1, \dots, $k-1$ DOROZHKI~1. (tEPERX ZONY 0, 
1, \dots, $k-1$ ZAPOLNENY, ZONA $k$ PUSTA.) aNALOGICHNAYA PROCEDURA 
ISPOLXZUETSYA DLYA ZAPOLNENIYA BUFERA VVODA DLYA DOROZHKI~2, KAK TOLXKO ON 
STANET PUSTYM. kOGDA BUFER VYVODA PODGOTOVLEN DLYA ZAPISI NA DOROZHKU~3, 
MY OBRASHCHAEM |TOT PROCESS, T. E. PROSMATRIVAEM $T1$ POKA NE NAJDETSYA PERVAYA 
\emph{PUSTAYA} ZONA NA DOROZHKE~$3$, SKAZHEM ZONA~$k$, I V TO ZHE VREMYA 
KOPIRUEM DANNYE IZ ZON 0, 1, \dots, $k-1$ NA $T2$. dANNYE
%%423
NA $T2$, K KOTORYM PRISOEDINYAETSYA SODERZHIMOE BUFERA VYVODA, ISPOLXZUYUTSYA 
TEPERX DLYA ZAPOLNENIYA ZONY $k$ NA DOROZHKE 3.

dLYA |TOJ PROCEDURY MY DOLZHNY UMETX PISATX V SEREDINU LENTY $T1$, NE 
RAZRUSHAYA POSLEDUYUSHCHUYU INFORMACIYU NA |TOJ LENTE. kAK I V SLUCHAE 
OSCILLIRUYUSHCHEJ SORTIROVKI S PRYAMYM CHTENIEM (P.~5.4.5), MOZHNO BEZ OPASENIJ 
VYPOLNYATX |TO DEJSTVIE, ESLI PRINYATX MERY PREDOSTOROZHNOSTI.

pOSKOLXKU PROSMOTR DO ZONY $k$ VYPOLNYAETSYA TOLXKO ODIN RAZ ZA KAZHDYE $2^k$ 
SHAGOV, TO, CHTOBY PEREPISATX $2^i-1$ BLOKOV S DOROZHKI 1 V PAMYATX, 
POTREBUETSYA PEREMESTITX LENTU NA $\sum_{v\le k<l} 2^{l-1-k}\cdot c \cdot 
2^k=cl2^{l-1}$, GDE $c$---NEKOTORAYA KONSTANTA. tAKIM OBRAZOM, KAZHDYJ PROHOD 
SLIYANIYA TREBUET $O(N\log N)$ SHAGOV. tAK KAK V SBALANSIROVANNOM SLIYANII 
IMEETSYA $O(\log N)$ PROHODOV, TO OBSHCHEE VREMYA RABOTU BUDET $O(N(\log 
N)^2)$, CHTO ASIMPTOTICHESKI ZNACHITELXNO LUCHSHE, CHEM NAIHUDSHIJ SLUCHAJ DLYA BYSTROJ 
SORTIROVKI.

nO NA SAMOM DELE |TOT METOD OKAZYVAETSYA POCHTI BESPOLEZNYM, ESLI 
PRIMENYAETSYA DLYA SORTIROVKI 100000 ZAPISEJ IZ PRIMERA P.~5.4.6, POSKOLXKU 
INFORMACIYA, KOTORAYA DOLZHNA RAZMESHCHATXSYA NA LENTE $T1$, NE UMESTITSYA NA 
ODNOJ BOBINE LENTY. i DAZHE ESLI MY PRENEBREZHEM |TIM FAKTOM I BUDEM 
ISHODITX IZ SAMYH OPTIMISTICHESKIH PREDPOLOZHENIJ OTNOSITELXNO SOVMESHCHENIYA 
CHTENIYA/ZAPISI/VYCHISLENIJ, OTNOSITELXNO DLIN MEZHBLOCHNYH PROMEZHUTKOV I T. D.,
 TO NAJDEM, CHTO DLYA VYPOLNENIYA SORTIROVKI POTREBUETSYA OKOLO 37~CH! iTAK, 
|TOT METOD PREDSTAVLYAET CHISTO AKADEMICHESKIJ INTERES: KONSTANTA V 
$O(N(\log N)^2)$ SLISHKOM VELIKA, CHTOBY METOD BYL UDOVLETVORITELEN DLYA 
PRAKTICHESKIH ZNACHENIJ $N$.

\section oDNOLENTOCHNAYA SORTIROVKA. mOZHNO LI OBOJTISX VSEGO ODNOJ LENTOJ? 
nETRUDNO VIDETX, CHTO SORTIROVKU METODOM PUZYRXKA $P$-GO PORYADKA MOZHNO 
PREOBRAZOVATX V ODNOLENTOCHNUYU SORTIROVKU, NO REZULXTAT BUDET UZHASEN.

g.~b.~dEMUT [Ph.~D.~thesis (Stanford University, 1956), 85] SDELAL 
NABLYUDENIE, CHTO V VYCHISLITELXNOJ MASHINE S OGRANICHENNOJ OPERATIVNOJ 
PAMYATXYU NELXZYA, UMENXSHITX CHISLO INVERSIJ PERESTANOVKI BOLXSHE, CHEM NA 
OGRANICHENNUYU VELICHINU, POSLE PROSMOTRA LENTY NA OGRANICHENNOE RASSTOYANIE; 
SLEDOVATELXNO, LYUBOJ ALGORITM SORTIROVKI S ODNOJ LENTOJ POTREBUET V 
SREDNEM PO KRAJNEJ MERE $dN^2$ EDINIC VREMENI (GDE $d$---NEKOTORAYA 
POLOZHITELXNAYA KONSTANTA, ZAVISYASHCHAYA OT KONFIGURACII evm).

r.~m.~kARP NASHEL OCHENX INTERESNYJ PODHOD K ISSLEDOVANIYU. |TOJ TEMY, 
OBNARUZHIV TO, CHTO, PO SUSHCHESTVU, YAVLYAETSYA \emph{OPTIMALXNYM} SPOSOBOM 
SORTIROVKI S ODNOJ LENTOJ. pRI OBSUZHDENII ALGORITMA kARPA UDOBNO 
SLEDUYUSHCHIM OBRAZOM PEREFORMULIROVATX ZADACHU: \emph{KAK BYSTREE VSEGO 
PEREVEZTI LYUDEJ MEZHDU |TAZHAMI, ESLI RABOTAET TOLXKO ODIN LIFT?}

%% 424

rASSMOTRIM ZDANIE S $n$ |TAZHAMI; POMESHCHENIE KAZHDOGO |TAZHA RASSCHITANO NA $c$ 
CHELOVEK. v |TOM ZDANII NET NI OKON, NI DVEREJ, NI LESTNIC, NO VSE ZHE ESTX 
LIFT, KOTORYJ MOZHET OSTANAVLIVATXSYA NA LYUBOM |TAZHE. v ZDANII NAHODYATSYA 
$cn$ CHELOVEK, I ROVNO $c$ IZ NIH HOTYAT POPASTX NA KAZHDYJ OTDELXNYJ |TAZH. v 
LIFT VMESHCHAETSYA SAMOE BOLXSHEE $b$ CHELOVEK, I ON ZATRACHIVAET ODNU EDINICU 
VREMENI DLYA PEREMESHCHENIYA S |TAZHA $i$ NA |TAZH $i+1$. mY HOTELI BY NAJTI 
BYSTREJSHIJ SPOSOB PEREMESTITX VSEH LYUDEJ NA NUZHNYE |TAZHI, ESLI TREBUETSYA, 
CHTOBY LIFT NACHAL I ZAKONCHIL SVOE DVIZHENIE NA PERVOM |TAZHE.

nETRUDNO ZAMETITX SVYAZX MEZHDU |TOJ ZADACHEJ I ODNOLENTOCHNOJ SORTIROVKOJ: 
LYUDI---|TO ZAPISI, ZDANIE---LENTA, |TAZHI--- OTDELXNYE, BLOKI NA LENTE, A 
LIFT---OPERATIVNAYA PAMYATX evm. dEJSTVIYAM PROGRAMM DLYA evm SVOJSTVENNA 
BOLXSHAYA GIBKOSTX, CHEM DEJSTVIYAM LIFTERA (ONA MOZHET, NAPRIMER, SOZDAVATX 
DVOJNIKOV ILI, RAZREZAV CHELOVEKA NA DVE CHASTI, OSTAVITX IH NA VREMYA NA 
RAZNYH |TAZHAH I T. D.); NO V PRIVODIMOM NIZHE ALGORITME ZADACHA RESHAETSYA 
BYSTREJSHIM MYSLIMYM SPOSOBOM BEZ VYPOLNENIYA TAKIH OPERACIJ. aLGORITM kARPA 
ISPOLXZUET SLEDUYUSHCHIE DVA VSPOMOGATELXNYH MASSIVA:
$$
\eqalign{
u_k, 1\le k\le n:& 
\rem{CHISLO LYUDEJ NA |TAZHAH  $\le k$, STREMYASHCHIHSYA POPASTX NA |TAZHI $>k$}\cr
d_k, 1\le k \le n:& 
\rem{CHISLO LYUDEJ NA |TAZHAH $\ge k$, STREMYASHCHIHSYA POPASTX NA |TAZHI $<k$}\cr
}
\eqno(4)
$$.
kOGDA LIFT PUST, MY VSEGDA IMEEM $u_k=d_{k+1}$ PRI $1\le k < n$, TAK KAK NA 
KAZHDOM |TAZHE NAHODYATSYA $c$ CHELOVEK; KOLICHESTVO LYUDEJ, NAPRAVLYAYUSHCHIHSYA S 
|TAZHEJ $\{1, \ldots, k\}$ NA |TAZHI $\{k+1, \ldots, P\}$, DOLZHNO RAVNYATXSYA 
CHISLU LYUDEJ, STREMYASHCHIHSYA PEREPRAVITXSYA V OBRATNOM NAPRAVLENII. pO 
OPREDELENIYU $u_n=d_1=0$.

yaSNO, CHTO LIFT DOLZHEN SDELATX PO KRAJNEJ MERE $\lceil u_k/b\rceil$ REJSOV 
S |TAZHA $k$ NA |TAZH $k+1$ PRI $1\le k<n$, TAK KAK TOLXKO $b$ PASSAZHIROV 
MOGUT PODNYATXSYA ZA ODIN REJS. aNALOGICHNO, ON DOLZHEN SDELATX NE MENEE 
$\lceil d_k/b\rceil$ REJSOV S |TAZHA $k$ NA |TAZH $k-1$. sLEDOVATELXNO, 
LIFTU POTREBUETSYA PO KRAJNEJ MERE
$$
\sum_{1\le k\le n} (\lceil u_k/n\rceil+\lceil d_k/b\rceil)
\eqno (5)
$$
EDINIC VREMENI PRI LYUBOM PRAVILXNOM GRAFIKE RABOTY. kARP OBNARUZHIL, CHTO 
|TA NIZHNYAYA GRANICA DEJSTVITELXNO DOSTIZHIMA, ESLI $u_1$, \dots,  $u_{n-1}$ NENULEVYE.

\proclaim tEOREMA k. eSLI $u_k>0$ PRI $1\le k <n$, TO SUSHCHESTVUET 
GRAFIK RABOTY LIFTA, PRI KOTOROM VSE LYUDI DOSTAVLYAYUTSYA NA SVOI |TAZHI ZA 
MINIMALXNOE VREMYA (5).
%%425

\bye