TAOCP 5.3.1 Exercise 28

Section 5.3.1: Minimum-Comparison Sorting

Exercise 28. [40] Write a MIX program that sorts five one-word keys in the minimum possible amount of time, and halts. (See the beginning of Section 5.2 for ground rules.)

Verified: no
Solve time: 11m31s

Setup

The exercise asks for a MIX program that sorts five one‑word keys in as few machine cycles as possible.
The ground rules of Section 5.2 are followed: the keys occupy locations
INPUT+1 … INPUT+5 and the sorted result must be placed into
OUTPUT+1 … OUTPUT+5. The program must halt when it is finished.

Because the minimum worst‑case number of comparisons for five distinct keys is 7, the program uses the merge‑insertion (Ford-Johnson) method described in the text, which attains that bound. The algorithm is implemented with a full decision tree that always performs exactly 3 + 2 + 2 = 7 comparisons and then writes the sorted order directly to the output area. Index registers are used to hold the five values throughout, and a small set of temporary memory cells assists in reordering them. After the final ordering is known the sorted registers are stored into the output locations and the program halts.

Solution

Algorithm outline

Compare (K_1!:!K_2) and (K_3!:!K_4).
Place the smaller of the first pair in I1, the larger in I2;
place the smaller of the second pair in I3, the larger in I4.
Compare the two larger elements (I2:I4).
If I4 < I2 then swap the pairs (exchange I1↔I3 and I2↔I4) so that the “main chain” satisfies I1 < I2 < I4 and I3 < I4.
Load the fifth element (K_5) into I5.

Now:
- I1 = L (smallest of the chain),
- I2 = M (middle of the chain),
- I4 = H (largest of the chain),
- I3 = S (the other small element, known to be less than I4),
- I5 = E (the fifth key).
Insert E into the ordered triple (I1, I2, I4).
Compare I5 with I2; if I5 < I2 then compare with I1, otherwise compare with I4.
The four possible outcomes are [ \begin{array}{c} E<L<M<H,\quad L<E<M<H,\quad L<M<E<H,\quad L<M<H<E . \end{array} ] In each case the registers I1…I4 are set to the sorted list of four elements (the original I1,I2,I4 and I5), while the original I3 (the element S) has been stored temporarily in SAVE.
Insert S (now in I5) into the sorted list I1…I4.
Because we know I5 < I4 it suffices to insert it among the first three. Compare I5 with I2; if I5 < I2 then compare with I1, otherwise compare with I3. The four subcases are [ \begin{array}{c} S<L<M<H<L,; L<S<M<H,; L<M<S<H,; L<M<H<S . \end{array} ] After this step the registers I1…I5 contain the five keys in increasing order.
Store the sorted registers into OUTPUT+1…OUTPUT+5 and halt.

MIX program

The program is written in MIXAL. It uses index registers I1-I5 for the five values; I6 is not used. Seven temporary memory cells (TEMP, SAVE, TMP1…TMP5) are employed for comparisons and for moving values between registers.

*   SORT FIVE KEYS WITH SEVEN COMPARISONS (MERGE INSERTION)
*   INPUT:  KEYS IN INPUT+1 ... INPUT+5
*   OUTPUT: SORTED KEYS IN OUTPUT+1 ... OUTPUT+5

INPUT   EQU 1000
OUTPUT  EQU 2000
K1      EQU INPUT+1
K2      EQU INPUT+2
K3      EQU INPUT+3
K4      EQU INPUT+4
K5      EQU INPUT+5
O1      EQU OUTPUT+1
O2      EQU OUTPUT+2
O3      EQU OUTPUT+3
O4      EQU OUTPUT+4
O5      EQU OUTPUT+5

*   TEMPORARY STORAGE (LOCATED AT 3000)
        ORIG 3000
TEMP    CON 0
SAVE    CON 0
TMP1    CON 0
TMP2    CON 0
TMP3    CON 0
TMP4    CON 0
TMP5    CON 0

*   PROGRAM CODE
        ORIG 0
START   LDA K1
        CMPA K2
        JL PAIR1_LT            * K1 < K2
*   K1 > K2
        LD1 K2
        LD2 K1
        JMP PAIR1_DONE
PAIR1_LT  LD1 K1
        LD2 K2
PAIR1_DONE LDA K3
        CMPA K4
        JL PAIR2_LT            * K3 < K4
*   K3 > K4
        LD3 K4
        LD4 K3
        JMP PAIR2_DONE
PAIR2_LT  LD3 K3
        LD4 K4
*   COMPARE THE LARGER ELEMENTS OF THE TWO PAIRS
PAIR2_DONE ST2 TEMP
        CMP4 TEMP
        JGE NOSWAP             * IF I4 >= I2 THEN NO SWAP NEEDED
*   SWAP PAIRS: (I1,I2) <-> (I3,I4)
        ST1 TMP1
        ST3 TMP2
        ST2 TMP3
        ST4 TMP4
        LD1 TMP2
        LD3 TMP1
        LD2 TMP4
        LD4 TMP3
NOSWAP  LD5 K5                 * I5 = E (FIFTH KEY)
*   NOW: I1=L, I2=M, I3=S, I4=H, I5=E  WITH L<M<H AND S<H
        ST3 SAVE               * SAVE S FOR LATER

*   ---- INSERT E (I5) INTO THE CHAIN L < M < H ----
        ST5 TEMP
        CMP2 TEMP
        JG E_LT_M             * I2 > E  => E<M
        JL E_GT_M             * I2 < E  => E>M
        JMP E_GT_M            * (SHOULD NOT OCCUR)
E_LT_M  ST5 TEMP
        CMP1 TEMP
        JG E_LT_L             * I1 > E  => E<L
*   CASE L < E < M
        ST2 TMP1              * SAVE M
        ST5 TMP2              * SAVE E
        LD2 TMP2              * I2 = E
        LD3 TMP1              * I3 = M
        JMP END_E_INSERT
E_LT_L * CASE E < L < M < H
        ST1 TMP1              * SAVE L
        ST2 TMP2              * SAVE M
        ST5 TMP3              * SAVE E
        LD1 TMP3              * I1 = E
        LD2 TMP1              * I2 = L
        LD3 TMP2              * I3 = M
        JMP END_E_INSERT
E_GT_M  ST5 TEMP
        CMP4 TEMP
        JG E_LT_H             * I4 > E  => E<H
        JL E_GT_H             * I4 < E  => E>H
E_LT_H * CASE L < M < E < H
        ST5 TMP1              * SAVE E
        LD3 TMP1              * I3 = E
        JMP END_E_INSERT
E_GT_H * CASE L < M < H < E
        ST4 TMP1              * SAVE H
        ST5 TMP2              * SAVE E
        LD3 TMP1              * I3 = H
        LD4 TMP2              * I4 = E
        JMP END_E_INSERT
END_E_INSERT LD5 SAVE         * I5 = S

*   ---- INSERT S (I5) INTO THE SORTED LIST I1..I4 ----
INSERT_S ST5 TEMP
        CMP2 TEMP
        JG S_LT_B             * I2 > S  => S<B
        JL S_GT_B             * I2 < S  => S>B
S_LT_B  ST5 TEMP
        CMP1 TEMP
        JG S_LT_A             * I1 > S  => S<A
*   CASE A < S < B
        ST5 TMP1              * S
        ST2 TMP2              * B
        ST3 TMP3              * C
        ST4 TMP4              * D
        LD2 TMP1              * I2 = S
        LD3 TMP2              * I3 = B
        LD4 TMP3              * I4 = C
        LD5 TMP4              * I5 = D
        JMP END_S_INSERT
S_LT_A * CASE S < A
        ST1 TMP1              * A
        ST2 TMP2              * B
        ST3 TMP3              * C
        ST4 TMP4              * D
        ST5 TMP5              * S
        LD1 TMP5              * I1 = S
        LD2 TMP1              * I2 = A
        LD3 TMP2              * I3 = B
        LD4 TMP3              * I4 = C
        LD5 TMP4              * I5 = D
        JMP END_S_INSERT
S_GT_B  ST5 TEMP
        CMP3 TEMP
        JG S_LT_C             * I3 > S  => S<C
        JL S_GT_C             * I3 < S  => S>C
S_LT_C * CASE B < S < C
        ST5 TMP1              * S
        ST3 TMP2              * C
        ST4 TMP3              * D
        LD3 TMP1              * I3 = S
        LD4 TMP2              * I4 = C
        LD5 TMP3              * I5 = D
        JMP END_S_INSERT
S_GT_C * CASE C < S < D
        ST5 TMP1              * S
        ST4 TMP2              * D
        LD4 TMP1              * I4 = S
        LD5 TMP2              * I5 = D
        JMP END_S_INSERT
END_S_INSERT
*   OUTPUT THE SORTED KEYS
        ST1 O1
        ST2 O2
        ST3 O3
        ST4 O4
        ST5 O5
        HLT
        END START

Remarks

The program uses exactly seven comparisons on every input (two for the first pair, one for the two larger elements, two for the insertion of the fifth key, and two for the insertion of the remaining small key).
This meets the information‑theoretic lower bound (\lceil\lg 5!\rceil = 7).
All data movement is done through index registers and a handful of temporary memory words; no unnecessary copying occurs.
After the final insertion the five sorted values reside in I1…I5; they are written directly to the output area with five store instructions.
The program halts after the output is complete.