\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$, 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 kM$,\cr }\cr Y_N&=\cases{ 0, & ESLI $N\le M$,\cr 3N+2+{1\over N}\sum_{0\le kM$.\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 kk$}\cr d_k, 1\le k \le n:& \rem{CHISLO LYUDEJ NA |TAZHAH $\ge k$, STREMYASHCHIHSYA POPASTX NA |TAZHI $0$ PRI $1\le k