%%off
* MMIX-Implementierung des Heapsort-Algorithmus
* =============================================
* von Jan-Hendrik Behrmann 2012
* M. Ruckert renamed to adapt to other programs 
        PREFIX	  :sort:

K	IS $0	* Adresse des Arrays
n	IS $1	* Anzahl der Elemente

l	IS $2	* linke Grenze des Heaps
r	IS $3	* rechte Grenze des Heaps
i	IS $4	* Position des aktuellen Knotens
k	IS $5	* Wert des aktuellen Knotens
j	IS $6	* Position des linken / größeren Kindes
kj	IS $7	* Wert des linken / größeren Kindes
j1	IS $8	* Position rechtes Kind
kj1	IS $9	* Wert des rechten Kindes
t	IS $10	* Hilfsvariable für Vergleiche

%%on
Sort	SLU r,n,3		\hfil$1$& \ul{\sl H1. Initialize.}
	SUB r,r,8		\hfil$1$& $r\is 8(n-1)$.
	SRU l,n,1		\hfil$1$&	
	SLU l,l,3		\hfil$1$& $l\is 8\lfloor n/2\rfloor$.
%%%
	BNP l,9F		\hfil$1$& Terminate if $n<2$.
%%	% l > 0; building the heap
1H	SUB l,l,8		\hfil$\lfloor N/2\rfloor$& $l\is l-1$,
	LDO k,K,l		\hfil$\lfloor N/2\rfloor$& $k\is k_l$,
%%	% replace subtree
	SET j,l	  		\hfil$\lfloor N/2\rfloor$&  \ul{\sl H3. Prepare for siftup.} $j\is l$,
	JMP 4F	  		\hfil$\lfloor N/2\rfloor$& 
%%%
5H	LDO kj,K,j  		\hfil$B+A$& Load $k_j$.
	BZ t,6F	 		\hfil$B+A+2D$& To H6 if $j = r$.
%%%
	ADD j1,j,8 		\hfil$B+A-D$& \ul{\sl H5. Find larger child.} 
	LDO kj1,K,j1 		\hfil$B+A-D$& Load $k_{j+1}$.
	CMP t,kj,kj1 		\hfil$B+A-D$& Compare $k_j:k_{j+1}$.
	CSNP j,t,j1		\hfil$B+A-D$& if $k_j< k_{j+1}$ $j\is j+1$.
	CSNP kj,t,kj1		\hfil$B+A-D$& if $k_j< k_{j+1}$ $k_j\is k_{j+1}$.
%%%
6H	CMP t,k,kj 		\hfil$B+A$& \ul{\sl H6. Larger than $K$?} 
	BNN t,8F 		\hfil$B+3A$& To H8 if $K\ge K_j$		
%%%
	STO kj,K,i 		\hfil$B$&  \ul{\sl H7. Move it up.} $R_i\is R_j$. 
%%	% Heapify current subtree
4H	SET i,j			\hfil$B+P$&  \ul{\sl H4. Advance downward.} $i\is j$.
	2ADDU j,j,8		\hfil$B+P$& $j\is 2j+8$.
	CMP t,j,r		\hfil$B+P$& Compare $j:r$.	
	PBNP t,5B		\hfil$B-2A+3P$& Jump if $j\le r$.		
%%	% k <= kj
8H	STO k,K,i		\hfil$P$&  \ul{\sl H8. Store $R$.} $K_i\is k$.
	BP l,1B			\hfil$P+2(\lfloor N/2\rfloor-1)$&  \ul{\sl H2. Decrease $l$ or $r$.} 
%%%
2H	LDO k,K,r		\hfil$N-1$& If $l=0$ $k\is K_r$,
	LDO t,K,0		\hfil$N-1$& $t\is K_0$,
	STO t,K,r		\hfil$N-1$& $K_r\is K_0$,
	SUB r,r,8		\hfil$N-1$& $r\is r-8$
%%	% if r > 0 -> Heapify
	SET j,0	  		\hfil$N-1$&  \ul{\sl H1. Prepare for siftup.} $j\is l$,
	PBP r,4B 		\hfil$N+1$& To H3 if $r>0$.
%%	% r = 0; done
	STO k,K,0		\hfil$1$& $K_0\is k$,	   
%%%
9H	POP 0,0
%%off