\input style
pIRAMIDALXNUYU SORTIROVKU INOGDA OPISYVAYUT KAK \hslogo-ALGORITM; |TO 
OBOZNACHENIE UKAZYVAET NA HARAKTER IZMENENIYA PEREMENNYH~$l$ I~$r$. vERHNIJ 
TREUGOLXNIK SOOTVETSTVUET FAZE  POSTROENIYA PIRAMIDY, KOGDA~$r=N$, A 
$l$~UBYVAET DO~$1$; NIZHNIJ TREUGOLXNIK PREDSTAVLYAET FAZU VYBORA, 
KOGDA~$l=1$, A $r$~UBYVAET DO~$1$. v TABL.~2 POKAZAN PROCESS PIRAMIDALXNOJ 
SORTIROVKI VSE  TEH ZHE SHESTNADCATI CHISEL. (v KAZHDOJ STROKE 
IZOBRAZHENO SOSTOYANIE POSLE SHAGA~H2, SKOBKI UKAZYVAYUT NA ZNACHENIYA 
PEREMENNYH~$l$ I~$r$.)

{\catcode`\[=\active\def[{\hbox to 0pt{\hss$\lbrack$}}
 \catcode`\]=\active\def]{\hbox to 0pt{$\rbrack$\hss}}
\def\cell#1{$\phantom{[}#1\phantom{]}$\bskip}
\htable{tABLICA 2}%
{pRIMER PIRAMIDALXNOJ SORTIROVKI}%
{
\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&%
\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&\cell{#}&%
\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\hfil\cr
 K_1 & K_2 & K_3 & K_4 & K_5 & K_6 & K_7 & K_8 & K_9 & K_{10} & K_{11} & K_{12} & K_{13} & K_{14} & K_{15} & K_{16} & l & r  & K  \cr
 503 & 087 & 512 & 061 & 908 & 170 & 897 &[275 & 653 & 426    & 154    & 509    & 612    & 677    & 765    & 703]   & 8 & 16 & 275\cr
 503 & 087 & 512 & 061 & 908 & 170 &[897 & 703 & 653 & 426    & 154    & 509    & 612    & 677    & 765    & 275]   & 7 & 16 & 897\cr
 503 & 087 & 512 & 061 & 908 &[170 & 897 & 703 & 653 & 426    & 154    & 509    & 612    & 677    & 765    & 275]   & 6 & 16 & 170\cr
 503 & 087 & 512 & 061 &[908 & 612 & 897 & 703 & 653 & 426    & 154    & 509    & 170    & 677    & 765    & 275]   & 5 & 16 & 908\cr
 503 & 087 & 512 &[061 & 908 & 612 & 897 & 703 & 653 & 426    & 154    & 509    & 170    & 677    & 765    & 275]   & 4 & 16 & 061\cr
 503 & 087 &[512 & 703 & 908 & 612 & 897 & 275 & 653 & 426    & 154    & 509    & 170    & 677    & 765    & 061]   & 3 & 16 & 512\cr
 503 &[087 & 897 & 703 & 908 & 612 & 765 & 275 & 653 & 426    & 154    & 509    & 170    & 677    & 512    & 061]   & 2 & 16 & 087\cr
[503 & 908 & 897 & 703 & 426 & 612 & 765 & 275 & 653 & 087    & 154    & 509    & 170    & 677    & 512    & 061]   & 1 & 16 & 503\cr
[908 & 703 & 897 & 653 & 426 & 612 & 765 & 275 & 503 & 087    & 154    & 509    & 170    & 677    & 512]   & 908    & 1 & 15 & 061\cr
[897 & 703 & 765 & 653 & 426 & 612 & 677 & 275 & 503 & 087    & 154    & 509    & 170    & 061]   & 897    & 908    & 1 & 14 & 512\cr
[765 & 703 & 677 & 653 & 426 & 612 & 512 & 275 & 503 & 087    & 154    & 509    & 170]   & 765    & 897    & 908    & 1 & 13 & 061\cr
[703 & 653 & 677 & 503 & 426 & 612 & 512 & 275 & 061 & 087    & 154    & 509]   & 703    & 765    & 897    & 908    & 1 & 12 & 170\cr
[677 & 653 & 612 & 503 & 426 & 509 & 512 & 275 & 061 & 087    & 154]   & 677    & 703    & 765    & 897    & 908    & 1 & 11 & 170\cr
[653 & 503 & 612 & 275 & 426 & 509 & 512 & 170 & 061 & 087]   & 653    & 677    & 703    & 765    & 897    & 908    & 1 & 10 & 154\cr
[612 & 503 & 512 & 275 & 426 & 509 & 154 & 170 & 061]& 612    & 653    & 677    & 703    & 765    & 897    & 908    & 1 &  9 & 087\cr
[512 & 503 & 509 & 275 & 426 & 087 & 154 & 170]& 512 & 612    & 653    & 677    & 703    & 765    & 897    & 908    & 1 &  8 & 061\cr
[509 & 503 & 154 & 275 & 426 & 087 & 061]& 509 & 512 & 612    & 653    & 677    & 703    & 765    & 897    & 908    & 1 &  7 & 170\cr
[503 & 426 & 154 & 276 & 170 & 087]& 503 & 509 & 512 & 612    & 653    & 677    & 703    & 765    & 897    & 908    & 1 &  6 & 061\cr
[426 & 275 & 154 & 061 & 176]& 426 & 503 & 509 & 512 & 612    & 653    & 677    & 703    & 765    & 897    & 908    & 1 &  5 & 087\cr
[275 & 170 & 154 & 061]& 275 & 426 & 503 & 509 & 512 & 612    & 653    & 677    & 703    & 765    & 897    & 908    & 1 &  4 & 087\cr
[170 & 087 & 154]& 170 & 275 & 426 & 503 & 509 & 512 & 612    & 653    & 677    & 703    & 765    & 897    & 908    & 1 &  3 & 061\cr
[154 & 087]& 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612    & 653    & 677    & 703    & 765    & 897    & 908    & 1 &  2 & 061\cr
[061]& 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612    & 653    & 677    & 703    & 765    & 897    & 908    & 1 &  1 & 061\cr
}}

\prog H.(pIRAMIDALXNAYA SORTIROVKA.) zAPISI, NAHODYASHCHIESYA V YACHEJKAH 
S~$|INPUT|+1$ PO~$|INPUT|+N$, SORTIRUYUTSYA PRI POMOSHCHI ALGORITMA~H; REGISTRY 
PRINIMAYUT SLEDUYUSHCHIE ZNACHENIYA: $|rI1|\equiv l-1$, $|rI2|\equiv r-1$, 
$|rI3|\equiv i$, $|rI4|\equiv j$, $|rI5|\equiv r-l$, $|rA|\equiv K \equiv R$, 
$|rX|\equiv R_j$.
\code
START & ENT1 & N/2       & 1           & H1. nACHALXNAYA USTANOVKA $l\asg \floor{N/2}+1$.
      & ENT2 & N-1       & 1           & $r\asg N$.
1H    & DEC1 & 1         & \floor{N/2} & $l\asg l-1$.
      & LDA  & INPUT+1,1 & \floor{N/2} & $R\asg R_l$, $K\asg K_l$.
3H    & ENT4 & 1,1       & P           & H3. pRIGOTOVITXSYA K "PROTASKIVANIYU". $j\asg l$.
      & ENT5 & 0,2       & P
      & DEC5 & 0,1       & P           & $|rI5|\asg r-j$.
%% 180
      & JMP  & 4r        & P           & k SHAGU~H4.
5H    & LDX  & INPUT 4   & B+A-D       & H5. nAJTI "BOLXSHEGO" SYNA.
      & CMPX & INPUT+1,4 & B+A-D
      & JOE  & 6F        & B+A-D       & pEREHOD, ESLI~$K_j\ge K_{j+1}$.
      & INC4 & 1         & C           & v PROTIVNOM SLUCHAE USTANOVITX~$j\asg j+1$.
      & DECS & 1         & C
9H    & LDX  & INPUT,4   & C+D         & $|rX|\asg R_j$.
6H    & CMPA & INPUT,4   & B+A         & H6. bOLXSHE~$K$?
      & JGE  & 8F        & B+A         & k H8, ESLI~$K\ge K_j$.
7H    & STX  & INPUT,3   & B           & H7. pODNYATX EGO VVERH. $R_i \asg R_j$. 
4H    & ENT3 & 0,4       & B+P         & H4. pRODVINUTXSYA   VNIZ.
      & DEC5 & 0,4       & B+P         & $|rI5|\asg|rI5|-j$.
      & INC4 & 0,4       & B+P         & $j\asg j+j$.
      & J5P  & 5B        & B+P         & k H5, ESLI~$j<r$.
      & J5Z  & 9B        & P-A+D       & k H6, ESLI~$j=r$.
8H    & STA  & INPUT,3   & P           & H8. zANESTI~$R$. $R_i\asg R$.
2H    & J1P  & 1v        & P           & H2. uMENXSHITX~$l$ ILI~$r$.
      & LDA  & INPUT+1,2 & N-1         & eSLI~$l=1$, TO USTANOVITX~$R\asg R_r$, $K\asg K_r$.
      & LDX  & INPUT+1   & N-1
      & STX  & INPUT+1,2 & N-1         & $R_r\asg R_1$.
      & DEC2 & 1         & N-1         & $r\asg r-1$.
      & J2P  & 3B        & N-1         & k H3, ESLI~$r>1$.
      & STA  & INPUT+1   & 1           & $R_1\asg R$.
\endcode
\progend

eTA PROGRAMMA PRIBLIZITELXNO LISHX VDVOE DLINNEE PROGRAMMY~S, NO PRI 
BOLXSHIH~$N$ ONA GORAZDO BOLEE |FFEKTIVNA. eE VREMYA RABOTY ZAVISIT OT
$$
\eqalign{
P &= N+\floor{N/2}-2 = \hbox{CHISLO "PROTASKIVANIJ"};\cr
A &= \hbox{CHISLO PROTASKIVANIJ, PRI KOTORYH KLYUCH~$K$ V KONCE POPADAET VO 
VNUTRENNIJ UZEL PIRAMIDY};\cr
B &=\hbox{SUMMARNOE CHISLO KLYUCHEJ, PROSMOTRENNYH VO VREMYA PROTASKIVANIJ;}\cr
C &= \hbox{CHISLO PRISVAIVANIJ~$j\asg j+1$ V SHAGE~H5};\cr
D &= \hbox{CHISLO SLUCHAEV, KOGDA V SHAGE~H4 $j=r$.}\cr
}
$$

eTI VELICHINY PROANALIZIROVANY NIZHE. kAK POKAZYVAET PRAKTIKA, ONI 
SRAVNITELXNO MALO OTKLONYAYUTSYA OT SVOIH SREDNIH ZNACHENIJ:
$$
\matrix{
A \approx 0.349 N;\hfill & B \approx N \log_2 N - 1.87 N;\hfill \cr
C \approx {1\over 2}N\log_2 N - 0.9N;\hfill & D \approx \ln N.\hfill\cr
}
\eqno(7)
$$
pRI~$N=1000$, NAPRIMER, CHETYRE |KSPERIMENTA SO SLUCHAJNYMI ISHODNYMI  
DANNYMI  POKAZALI SOOTVETSTVENNO  REZULXTATY 
$(A, B, C, D)=(371, 8055, 4056, 12)$, $(351, 8072, 4087, 14)$, 
$(341, 8094, 4017, 8)$, $(340, 8108, 4083, 13)$. oBSHCHEE VREMYA RABOTY
%% 181
\bye