* List Merge Sort * TAOCP 5.2.4 * * Author: Armin Grodon * Version: 1.0 aR IS $0 address of records aO IS $1 address of output N IS $2 number of records aL IS $3 address of links s IS $4 t IS $5 p IS $6 link after s q IS $7 link after t tmp IS $8 l IS $9 o IS $10 offset in memory Kp IS $11 record at p Kq IS $12 record at q T IS $13 (N+1)*8 Merge CMP tmp,N,1 1 BNP tmp,End 1 * Proceed for N >= 2 ADD T,N,1 1 SLU T,T,3 1 SUB aR,aR,8 1 ADD aL,aO,T 1 * Initialize L * 1*8,-3*8,-4*8,-5*8,-6*8,...,-N*8,0,0,2*8 SET tmp,0 1 SLU o,N,3 1 STO tmp,aL,o 1 SUB o,o,8 1 STO tmp,aL,o 1 ADD tmp,tmp,8 1 STO tmp,aL,0 1 ADD tmp,tmp,8 1 ADD o,o,16 1 STO tmp,aL,o 1 SLU tmp,N,3 1 NEG tmp,0,tmp 1 SUB o,o,24 1 JMP 1F 1 0H STO tmp,aL,o N-2 ADD tmp,tmp,8 N-2 SUB o,o,8 N-2 1H PBP o,0B N-2 * Start sort * Begin new pass L2 SET s,0 A+1 SET t,T A+1 LDO p,aL,s A+1 LDO q,aL,t A+1 BZ q,End A+1 * Compare Kp:Kq L3Q LDO Kq,aR,q C''+B' L3P LDO Kp,aR,p C CMP tmp,Kp,Kq C BP tmp,L6 C * Advance p (p>=q) L4 NEG tmp,0,p C' LDO l,aL,s C' CSP tmp,l,p C' STO tmp,aL,s C' SET s,p C' LDO p,aL,p C' PBP p,L3P C' * Complete the sublist STO q,aL,s B' SET s,t B' L5 SET t,q D' LDO q,aL,q D' BP q,L5 D' JMP L8 B' * Advance q (q