%%off
%	Program 5.2.4L
%	Author M. Ruckert
%       instead of negative links, we use odd links
%       inside the inner loop, we do not set the odd-bit
%	on the first link in each run, since this would be to
%	expensive. Instead we keep a pointer $s_0$ to the head of each
%	run and apply the marker bit after the run is finished.
%	records are one OCTA with the first TETRA being the key and the second TETRA the link
%	links are offsets relative to the start of the array
%	two extra records R_0 and R_{n+1} are used as list heads. 
	
	PREFIX	:sort:
R	IS	$0
n	IS	$1

K	IS	R
L	IS	$2
p	IS	$3
q	IS	$4
kp	IS	$5
kq	IS	$6
s	IS	$7
Ln1	IS	s
s0	IS	$8
t	IS	$9
c	IS	$19

%%on
Sort	SL	n,n,3	   \hfil$1$&		\ul{\sl L1. Prepate two lists.}
	ADDU	L,K,4	   \hfil$1$&		$L\is L_0$.		   
%%
	SUB	p,n,16	   \hfil$1$&		$p\is n-2$.
	BN	p,9F	   \hfil$1$&		Terminate if $n<2$.
	OR	q,n,1	   \hfil$1$&		$q\is n^-$.
0H	STTU	q,L,p	   \hfil$N-2$&		$L_p\is q$.
	SUB	q,q,8	   \hfil$N-2$&		$q\is (q-1)^-$.
	SUB	p,p,8	   \hfil$N-2$&		$p\is p-1$.
	PBP	p,0B	   \hfil$N$&		Repeat until $p=0$.
%%%
	SET	c,8|1	   \hfil$1$&		
	STTU	c,L,0	   \hfil$1$&		$L_0\is 1^-$.
	SUB	c,n,8	   \hfil$1$&		
	ADDU	Ln1,c,L	   \hfil$1$&		$L_{n-1}\is L+8(n-1)$.
	SET	c,16|1	   \hfil$1$&
	STTU	c,Ln1,16   \hfil$1$&		$L_{n+1}\is 2^-$.		
	SET	c,0|1	   \hfil$1$&		
	STTU	c,Ln1,8	   \hfil$1$&		$L_n\is 0^-$.		
	STTU	c,Ln1,0	   \hfil$1$&		$L_{n-1}\is 0^-$.		
	JMP	L2	   \hfil$1$&
%%%
L3	CMP	c,kp,kq	   \hfil$C$&		\ul{\sl L3. Compare $K_p:K_q$.}
	BP	c,L6	   \hfil$C$&
	STTU	p,L,s	   \hfil$C^\prime$&	\ul{\sl L4. Advance $p$.} $L_s\is p$.
	SET	s,p	   \hfil$C^\prime$&	$s\is p$.
	LDTU	p,L,p	   \hfil$C^\prime$&	$p\is L_p$.
	LDT	kp,K,p	   \hfil$C^\prime$&	$k_p\is K_p$.
	PBEV	p,L3	   \hfil$C^\prime$&	If $p^+$, return to L3.
%%%
	STTU	q,L,s	   \hfil$B^\prime$&	\ul{\sl L5. Complete the sublist.} $L_s\is q$.
	SET	s,t	   \hfil$B^\prime$&	$s\is t$.
0H	SET	t,q	   \hfil$D^\prime$&	$t\is q$.
	LDTU	q,L,q	   \hfil$D^\prime$&	$q\is L_q$
	BEV	q,0B	   \hfil$D^\prime$&	Repeat until $q^-$.
	LDT	kq,K,q	   \hfil$B^\prime$&
	JMP	L8	   \hfil$B^\prime$&	
%%%
L6	STTU	q,L,s	   \hfil$C^{\prime\prime}$&	\ul{\sl L6. Advance $q$.} $L_s\is q$.
	SET	s,q	   \hfil$C^{\prime\prime}$&	$s\is q$.
	LDTU	q,L,q	   \hfil$C^{\prime\prime}$&	$q\is L_q$.
	LDT	kq,K,q	   \hfil$C^{\prime\prime}$&	$k_q\is K_q$.
	PBEV	q,L3	   \hfil$C^{\prime\prime}$&	If $q^+$, return to L3.
%%%
	STTU	p,L,s	   \hfil$B^{\prime\prime}$&	\ul{\sl L7. Complete the sublist.}  $L_s\is p$.
	SET	s,t	   \hfil$B^{\prime\prime}$&	$s\is t$.
0H	SET	t,p	   \hfil$D^{\prime\prime}$&	$t\is p$.
	LDTU	p,L,p	   \hfil$D^{\prime\prime}$&	$p\is L_p$
	BEV	p,0B	   \hfil$D^{\prime\prime}$&	Repeat until $p^-$.
	LDT	kp,K,p	   \hfil$B^{\prime\prime}$&
%%%
L8	LDTU	c,L,s0	   \hfil$B$&		\ul{\sl L8. End of pass?}
	OR	c,c,1	   \hfil$B$&		
	STTU	c,L,s0	   \hfil$B$&		$L_{s_0}\is L_{s_0}^-$.
	SET	s0,s	   \hfil$B$&		$s_0\is s$.
	ANDN	p,p,1	   \hfil$B$&		$p\is p^+$.		
	ANDN	q,q,1	   \hfil$B$&		$q\is q^+$.
	PBNZ	q,L3	   \hfil$B$&		If $q\ne 0$, go to L3.
	SET	c,1	   \hfil$A$&		
	STTU	c,L,t	   \hfil$A$&		$L_t\is 0^-$.
	OR	p,p,1	   \hfil$A$&
	STTU	p,L,s	   \hfil$A$&		$L_s\is p^-$.
%%%
L2	SET	s,0	   \hfil$A+1$&		\ul{\sl L2. Begin new pass.} $s\is 0$.
	SET	s0,s	   \hfil$A+1$&		$s_0\is s$.
	ADDU	t,n,8	   \hfil$A+1$&		$t\is n-1$.
	LDTU	p,L,s	   \hfil$A+1$&		$p\is L_s$.
	ANDN	p,p,1	   \hfil$A+1$&		$p\is p^+$.
	LDTU	q,L,t	   \hfil$A+1$&		$q\is L_t$.
	ANDN	q,q,1	   \hfil$A+1$&		$q\is q^+$.
	LDT	kp,K,p	   \hfil$A+1$&		$k_p\is K_p$.
	LDT	kq,K,q	   \hfil$A+1$&		$k_q\is K_q$.
	PBNZ	q,L3	   \hfil$A+3$&		Terminate if $q=0$.
%%%
9H	POP	0,0
%%off