%Author: Blake Hegerle <bhegerle@ea...>
%Re: MMIX Program for Algorithm 5.2.1S: Straight insertion sort  
%2005-10-28 17:53

% The penultimate and ultimate branches should probably be PBs. That is:
%        BNZ     t,3B            % Then to S3.
% and
%        BNP     t,2B
% should probably be PBNZ and PBNP, respectively. :-)
%
% Blake Hegerle


% An implementation of Algorithm 5.2.1S from TAOCP
% Straight insertion sort.

N       IS      16*8

i       IS      $0
j       IS      $1
K       IS      $2
R       IS      $2
Ki      IS      $3
Ri      IS      $3
t       IS      $255

INPUT   GREG    Data_Segment-8

        LOC     #100

Main    SET     j,8*2           % S1. Loop on j. j <- 2.

2H      SUBU    i,j,8           % S2. Set up i, K, R. i <- j - 1
        LDOU    K,INPUT,j

3H      LDOU    Ki,INPUT,i      % S3. Compare K : K_i.
        CMP     t,K,Ki          % Is K >= K_i?
        BNN     t,5F            % Then to S5.

4H      ADDU    t,i,8           % S4. Move R_i, decrease i. t <- i + 1
        STOU    Ri,INPUT,t      % R_{i+1} <- R_i
        SUBU    i,i,8           % i <- i - 1
        CMP     t,i,0           % Is i < 0?
        BNZ     t,3B            % Then to S3.

5H      ADDU    t,i,8           % S4. R into R_{i+1}
        STOU    R,INPUT,t

        INCL    j,8             % 2 <= j <= N
        CMPU    t,j,N
        BNP     t,2B

        TRAP    0,Halt,0

        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