%%%off % Copyright: This file is part of the MMIX Supplement package (c) Martin Ruckert 2014 % File: 5.2.1/ex33insert.mms % Author: M.Ruckert, 26.3.2012 % Title: Exercise 33, Optimized Straight Insertion Sort % 5.2.1 Page 81 key IS $0 n IS$1 j IS $2 scaled i IS$3 k IS $4 ki IS$5 key0 IS $6 t IS$7 %%% %\r0=R, \r1=N\hidewidth &&&Parameter. %%\mmsskip %\r2=j, \r3=i, \r4=k, \hidewidth &&& Local variables. %\r5={k_j}, \r6={R_{-1}} %%\mmsskip %%%on :Sort SUBU key0,key,8 1 & $\.key0.\is\.LOC($K_0$).$. SL j,n,3; SUB j,j,16 1 & $j\is N-1$. JMP S1 1 & %%% S2 ADD i,j,8 N-1 & \foolit{j}\ut S2. Set up \setfool, $K$, $R$.\\ LDO k,key,j N-1 & JMP S3 N-1 & %%% S4 STO ki,key0,i B &\ut S4. Move $R_i$, increase $i$.\\ ADD i,i,8 B & S3 LDO ki,key,i B+N-1 & \ut S3. Compare $K : K_i$.\\ CMP t,k,ki B+N-1 & PBP t,S4 B+N-1\bg{N-1} & STO k,key0,i N-1 & \ut S5. $R$ into $R_{i-1}$.\\ %%% SUB j,j,8 N-1 & S1 PBNN j,S2 N\bg{1} &\foolit{j}\ut S1. Loop on \setfool.\\\quad\slug %%% %%%rt 5.2.1ex33insert.rt & (5B+11N-4)\upsilon + (2B+3N-3)\mu %%%off POP 0,0 &