% Author: Blake Hegerle % MMIX Program for Algorithm 5.2.1L: List insertion sort. % 2005-11-22 21:41 % An implementation of Algorithm 5.2.1L from TAOCP % List insertion sort. N1 IS 16 N IS 16*8 j IS $1 p IS $2 q IS $3 K IS $4 Kp IS $5 t IS $255 INPUT GREG Data_Segment-8 LOC Data_Segment OCTA 503 OCTA 087 OCTA 512 OCTA 061 OCTA 908 OCTA 170 OCTA 897 OCTA 275 OCTA 653 OCTA 426 OCTA 154 OCTA 509 OCTA 612 OCTA 677 OCTA 765 OCTA 703 L GREG @ LOC #100 Main SET j,N % L1. Loop on j. j <- N. STOU j,L % L_0 <- N. STCO 0,L,j % L_N <- 0. JMP 6F % Go to decrease j. 2H LDOU p,L % L2. Set up p, q, K. p <- L_0. SET q,0 % q <- 0. LDOU K,INPUT,j % K <- K_j. 3H LDOU Kp,INPUT,p % L3. Compare K : K_p. CMPU t,K,Kp % Is K <= K_p? BNP t,5F % Then to L5. 4H SET q,p % L4. Bump p, q. q <- p. LDOU p,L,q % p <- L_q. CMPU t,p,0 % Is p > 0? PBP t,3B % Then to L3. 5H STOU j,L,q % L5. Insert into list. L_q <- j. STOU p,L,j % L_j <- p. 6H SUBU j,j,8 % Decrease j. CMPU t,j,0 % Is j > 0? PBP t,2B % Then repeat L2-L5. TRAP 0,Halt,0