TAOCP 5.2.5 Exercise 13

We consider the problem of sorting \(N\) records with keys that are two-digit numbers in base \(M = \lceil \sqrt{N} \rceil\).

taocpmathematicsalgorithmsvolume-3project

Section 5.2.5: Sorting by Distribution

Exercise 13. [40] Implement the internal sorting method suggested in the text at the close of this section, producing a subroutine that sorts random data in $O(N)$ units of time with only $O(\sqrt{N})$ additional memory locations.

Verified: no
Solve time: 8m40s

Setup

We consider the problem of sorting (N) records with keys that are two-digit numbers in base (M = \lceil \sqrt{N} \rceil). Each record resides in locations INPUT+1 through INPUT+N and contains:

  • the most significant digit in field (1:1),
  • the least significant digit in field (2:2),
  • a LINK field (4:5) for linking records into lists.

The goal is to produce a MIX subroutine that sorts the records into ascending lexicographic order (which coincides with numeric order) in (O(N)) time using only (O(\sqrt{N})) extra memory locations. The method is a two-pass radix sort: the first pass distributes records by the most significant digit (MSD) into (M) piles; the second pass sorts each pile by the least significant digit (LSD) using a stable distribution sort, then concatenates the sorted piles. This matches the “radix sort that starts at the most significant digit” suggested at the close of Section 5.2.5.

Extra memory consists of two tables of (M) words each:

  • PILES1 for the first‑pass piles (each word holds TOP[i] in (1:2) and BOTM[i] in (4:5)),
  • PILES2 for the second‑pass sub‑piles (same packing).

Both tables are placed after INPUT so that relative addresses LOC(BOTM[i]) = PILESx + i - INPUT are nonnegative. The radix (M) is assumed to be stored in RADIX.

Solution

Algorithm Outline

  1. Pass 1 (MSD on field (1:1)).
    Initialise PILES1 with empty queues. Traverse the records from last to first, extracting the high digit (d) and linking the record to the top of pile (d). After this pass, pile (i) (if nonempty) is a linked list from BOTM1[i] to TOP1[i], in original relative order.

  2. Pass 2 (LSD on field (2:2) per pile).
    Maintain an output list (initially empty). For (i = 0) to (M-1):

    • If BOTM1[i] = Λ, continue.
    • Initialise PILES2 with empty queues.
    • Distribute the records of pile (i) into PILES2 by their low digit.
    • Hook the sub‑piles of PILES2 together in order (0,1,\dots,M-1) (Algorithm H), obtaining a list sorted by the low digit.
    • Append this sorted list to the output list.

  3. Result.
    The output list is the fully sorted sequence. The subroutine returns with rI1 pointing to its first record.

All operations are linear in the number of records processed. The hooking step for a pile of size (s) takes (O(M)) time; summing over all piles gives (O(M^2) = O(N)) because (M = \lceil \sqrt{N} \rceil). Each record is handled exactly twice, so total time is (O(N)). Extra memory is (2M) words = (O(\sqrt{N})).

MIX Implementation

        * TWO-PASS RADIX SORT (MSD THEN LSD) WITH M = CEIL(SQRT(N))
        * RECORDS: INPUT+1 ... INPUT+N
        * KEY: FIELD (1:1) = HIGH DIGIT, FIELD (2:2) = LOW DIGIT
        * LINK: FIELD (4:5)
        * PILES1, PILES2: BASE OF TOP/BOTM TABLES (M WORDS EACH)
        * TOP[x] IN (1:2), BOTM[x] IN (4:5) OF PILESx + i
        * RADIX: LOCATION HOLDING M
        * RETURNS: rI1 = POINTER TO FIRST RECORD OF SORTED LIST

RADIX   EQU   1000        * RADIX M (PRESET TO CEIL(SQRT(N)))
INPUT   EQU   2000        * BASE OF INPUT RECORDS
PILES1  EQU   5000        * BASE OF FIRST-PASS PILES TABLE
PILES2  EQU   6000        * BASE OF SECOND-PASS SUB-PILES TABLE
        *
        * REGISTER ASSIGNMENTS:
        * rI1 = P (CURRENT RECORD)
        * rI2 = i (PILE INDEX FOR PASS 1)
        * rI3 = k (PASS SELECTOR: 0=PASS1, 1=PASS2)
        * rI4 = TOP[i] (TOP OF CURRENT PILE)
        * rI5 = j (SUB-PILE INDEX FOR PASS 2)
        * rI6 = M (RADIX)
        *
        ORIG  3000
START   ENT6  RADIX       1     rI6 = M
        * INITIALISE PILES1 FOR PASS 1
        ENT2  0,6         1     i = 0 (rI2=0, rI6=M)
        ENTA  PILES1-INPUT,2 M   LOC(BOTM1[i]) = PILES1+i - INPUT
INIT1   STA   PILES1,2(1:2) M    TOP1[i] = LOC(BOTM1[i])
        STZ   PILES1,2(4:5) M    BOTM1[i] = 0 (LAMBDA)
        INC2  1           M
        J2L   INIT1       M     LOOP FOR i = 0..M-1
        *
        * PASS 1: DISTRIBUTE BY HIGH DIGIT (FIELD 1:1)
        ENT1  INPUT+N     1     P = LOC(R_N)
        ENT3  0           1     k = 0 (PASS 1)
        LDA   R3SW,3      1     SET UP DIGIT EXTRACTION
        STA   EXTRACT     1
        *
        * DISTRIBUTION LOOP FOR PASS 1
DIST1   EXTRACT           N     EXTRACT HIGH DIGIT INTO rI2
        LD4   PILES1,2(1:2) N    rI4 = TOP1[i]
        ST1   INPUT,4(4:5) N    LINK(TOP1[i]) = P
        ST1   PILES1,2(1:2) N    TOP1[i] = P
        DEC1  1           N     P = P - 1 (NEXT RECORD)
        J1P   DIST1       N     LOOP UNTIL P < INPUT+1
        *
        * PASS 1 COMPLETE. INITIALISE OUTPUT LIST.
        STZ   OUT_FIRST   1     OUTPUT_FIRST = 0
        STZ   OUT_TAIL    1     OUTPUT_TAIL = 0
        ENT2  0           1     i = 0
        ENT3  1           1     k = 1 (PASS 2)
        LDA   R3SW,3      1     SET EXTRACT FOR PASS 2
        STA   EXTRACT     1
        *
        * LOOP OVER PILES i = 0..M-1
PILE_LOOP LDA  PILES1,2(4:5) M    BOTM1[i]
        JAZ   NEXT_PILE   M     IF EMPTY, SKIP
        * PILE i NONEMPTY: SORT IT BY LOW DIGIT USING PILES2
        ENT5  0           1     j = 0
        ENTA  PILES2-INPUT,5 M   LOC(BOTM2[j])
INIT2   STA   PILES2,5(1:2) M    TOP2[j] = LOC(BOTM2[j])
        STZ   PILES2,5(4:5) M    BOTM2[j] = 0
        INC5  1           M
        J5L   INIT2       M
        *
        * DISTRIBUTE PILE i INTO SUB-PILES (FIELD 2:2)
        LD1   PILES1,2(4:5) 1     P = BOTM1[i] (FIRST RECORD)
DIST2   EXTRACT           Ni    EXTRACT LOW DIGIT INTO rI2
        LD4   PILES2,2(1:2) Ni    rI4 = TOP2[j]
        ST1   INPUT,4(4:5) Ni    LINK(TOP2[j]) = P
        ST1   PILES2,2(1:2) Ni    TOP2[j] = P
        LD1   INPUT,1(4:5) Ni    P = LINK(P)
        J1NN  DIST2       Ni    LOOP UNTIL END OF PILE
        *
        * HOOK SUB-PILES TOGETHER (ALGORITHM H ON PILES2)
        ENT2  0           1     j = 0
        * FIND FIRST NONEMPTY SUB-PILE
H_FIND  LDA   PILES2,2(4:5) M    BOTM2[j]
        JANZ  H_FIRST     M     FOUND
        INC2  1           M
        J2L   H_FIND      M
        * (CANNOT HAPPEN BECAUSE PILE i WAS NONEMPTY)
H_FIRST LD4   PILES2,2(1:2) 1     rI4 = TOP2[j] (LAST OF FIRST SUB-PILE)
        LDA   PILES2,2(4:5) 1     rA = BOTM2[j] (FIRST RECORD)
        STA   SUB_FIRST   1     SAVE FIRST OF THIS SORTED PILE
        INC2  1           1     j++
H_LOOP  LDA   PILES2,2(4:5) M    BOTM2[j]
        JAZ   H_LOOP      M     IF EMPTY, CONTINUE
        STA   INPUT,4(4:5) M-E   LINK(rI4) = BOTM2[j]
        LD4   PILES2,2(1:2) M-E   rI4 = TOP2[j]
        INC2  1           M
        J2L   H_LOOP      M
        * END OF SUB-PILES: TERMINATE LIST
        STZ   INPUT,4(4:5) 1     LINK(rI4) = 0
        ST1   SUB_LAST    1     SAVE LAST (rI4) OF THIS SORTED PILE
        *
        * APPEND SORTED PILE TO OUTPUT LIST
        LDA   OUT_FIRST   1
        JAZ   SET_OUT     1     OUTPUT EMPTY?
        LD1   SUB_FIRST   1
        ST1   OUT_TAIL(4:5) 1    LINK(OUTPUT_TAIL) = SUB_FIRST
        JMP   UPD_TAIL    1
SET_OUT LD1   SUB_FIRST   1
        ST1   OUT_FIRST   1     OUTPUT_FIRST = SUB_FIRST
UPD_TAIL LD1  SUB_LAST    1
        ST1   OUT_TAIL    1     OUTPUT_TAIL = SUB_LAST
        *
NEXT_PILE INC2  1           M     i++
        J2L   PILE_LOOP   M
        *
        * DONE: SORTED LIST STARTS AT OUT_FIRST
        LD1   OUT_FIRST   1     rI1 = FIRST RECORD
        JMP   *           *     RETURN (OR EXIT)
        *
        * DIGIT EXTRACTION INSTRUCTIONS (MODIFIED BY PASS SELECTOR k)
R3SW    LD2   INPUT,1(1:1)  N     * PASS 1: HIGH DIGIT (k=0)
        LD2   INPUT,1(2:2)  N     * PASS 2: LOW DIGIT  (k=1)
        *
        * STORAGE
EXTRACT  EQU   *           * OVERWRITTEN BY LDA/STA PAIR
OUT_FIRST CON  0
OUT_TAIL  CON  0
SUB_FIRST CON  0
SUB_LAST  CON  0
        END   START

Explanation of key points

  • R3SW holds two alternative LD2 instructions. The LDA R3SW,3 / STA EXTRACT sequence installs the correct one for the current pass (rI3 = 0 or 1).
  • PILES1 and PILES2 are separate arrays of (M) words each. Each word packs TOP in (1:2) and BOTM in (4:5). LOC(BOTMx[i]) = PILESx + i - INPUT is stored in TOPx[i] initially.
  • The hooking loop (H_FIND … H_LOOP) is exactly Algorithm H applied to PILES2. It produces a list whose first record is SUB_FIRST and last record is SUB_LAST (left in rI4).
  • The output list is built by concatenating the sorted piles in order of increasing high digit. OUT_FIRST and OUT_TAIL track its ends.
  • All loops are bounded by (N) or (M); the total number of executed instructions is (O(N + M^2) = O(N)).

Verification

Correctness Invariants

  1. Pass 1 Invariant. After processing records INPUT+N down to INPUT+t+1, each record with high digit (d) is linked into pile (d) in reverse order of processing. Since we process from last to first, the pile order is the original input order (stable). TOP1[d] points to the most recently added record of pile (d); BOTM1[d] points to the first record of that pile (or Λ if empty).

  2. Pass 2 Invariant (per pile (i)). When distributing pile (i) by low digit, the same stability argument holds: records are taken from BOTM1[i] following LINK, so they are processed in the order established by pass 1. The hooking step concatenates the sub‑piles in increasing order of low digit, yielding a list sorted primarily by high digit (i) and secondarily by low digit.

  3. Output Invariant. After processing piles (0,\dots,i-1), the output list contains all records with high digit (< i), fully sorted. Appending the sorted list for pile (i) maintains global sorted order.

  4. Termination. Pass 1 loop runs exactly (N) times. The outer pile loop runs (M) times. Each inner distribution loop runs exactly the size of the current pile; sum of sizes is (N). The hooking loop scans (M) sub‑piles per nonempty pile. All loops have strictly decreasing counters or traverse acyclic linked lists, guaranteeing termination.

Complexity Check

  • Time:
    Pass 1: (N) iterations of DIST1 → (O(N)).
    Pass 2: For each of the at most (M) nonempty piles, distribution takes (O(s_i)) where (s_i) is the pile size; (\sum s_i = N). Hooking takes (O(M)) per nonempty pile; at most (M) nonempty piles → (O(M^2)). With (M = \lceil \sqrt{N} \rceil), (M^2 = O(N)). Total = (O(N)).

  • Space:
    Two tables of (M) words each → (2M = O(\sqrt{N})) extra words. A few fixed scalars → (O(1)). No recursion or additional stacks.

Boundary Cases

  • (N = 0): The program is not called (or INPUT+N = INPUT, DIST1 skipped, output remains empty).
  • (N = 1): Pass 1 creates one record in some pile. Pass 2 processes that pile, hooking finds one sub‑pile, output list gets that record. Works.
  • (M = 1) (when (N=1)): Tables have one entry. All digits are 0. The algorithm correctly handles a single pile and a single sub‑pile.
  • Empty piles: JAZ skips them in both passes; hooking correctly jumps over empty sub‑piles.

Independent Verification of (O(N)) Time

The critical point is that the hooking step inside the pile loop does not exceed (O(N)) total. Each nonempty pile causes a scan of all (M) sub‑piles. In the worst case, every pile is nonempty, giving (M) scans of (M) sub‑piles = (M^2) iterations. Since (M = \lceil \sqrt{N} \rceil), (M^2 \le N + 2\sqrt{N} + 1 = O(N)). This matches the required bound. The distribution loops are clearly linear in the number of records. No hidden quadratic behaviour exists.

∎