TAOCP 5.4.7 Exercise 6

Section 5.4.7: External Radix Sorting

Exercise 6. ▶ [20] A certain file contains two-digit keys 00, 01, . . . , 99. After performing Mauchly’s radix sort on the least significant digits, we can repeat the same scheme on the most significant digits, interchanging the roles of tapes T2 and T4. In what order will the keys finally appear on T2?

Verified: no
Solve time: 12m23s

Solution

We first analyze Mauchly's read-backward radix sort for 10 keys (0-9) on four tapes. The algorithm is given by the table in the text (Section 5.4.7). The passes are:

• Pass 1: Read T2 (initial tape), distribute: T1←{4,5}, T3←{2,3,6,7}, T4←{0,1,8,9}.
• Pass 2: Read T3, distribute: T1←{2,7} (appended), T2←{3,6}.
• Pass 3: Read T4, distribute: T1←{0,9} (appended), T3←{1,8}.
• Pass 4: Read the last group of T1 ({0,9}), split into singletons onto T4: T4←{9}{0}.
• Pass 5: (Implied by the garbled line and the collection phase) Read the remaining groups on T1 ({2,7} then {4,5}), T2 ({3,6}), and T3 ({1,8}), split all into singletons onto T4.
• Collection: Concatenate the singletons on T4 in order 0,1,…,9.

Each key is read (backwards) once per pass it participates in. The number of reads equals the depth of its external node in the 4‑lifo tree. Counting the passes for each digit:

In a read‑backward radix sort, a key is stable (preserves the original order of equal keys) if its depth is even, and anti‑stable (reverses the order) if its depth is odd. Hence Mauchly’s sort is stable for digits 4 and 5, anti‑stable for digits 0,1,2,3,6,7,8,9.

Now consider the two‑digit file 00,01,…,99 initially in increasing order on T2.
First pass (LSD): Mauchly’s sort on the units digit. Because all 100 keys are distinct, the output is grouped by LSD = 0,1,…,9. Within the group for LSD = ℓ, the keys are either in the original MSD order (0ℓ,1ℓ,…,9ℓ) if ℓ is stable, or reversed (9ℓ,8ℓ,…,0ℓ) if ℓ is anti‑stable.
Second pass (MSD): The same scheme is applied to the tens digit, but with tapes T2 and T4 interchanged. The input to this pass is the LSD‑sorted file (now on T4). The stability pattern for the MSD digits is exactly the same as for the LSD digits (the tree structure is unchanged by swapping T2 and T4). Thus MSD digits 4 and 5 are stable; the other eight are anti‑stable.

The LSD‑sorted file is ordered by increasing LSD. For a fixed MSD = d, the keys with that MSD appear in the order of increasing LSD, because the LSD groups are concatenated in order 0,1,…,9 and each group contains exactly one key with MSD = d. Therefore the input order for MSD = d is always

[ 10d+0,;10d+1,;\dots,;10d+9 ]

(ascending LSD), regardless of the first pass’s stability.

The second pass groups by MSD and outputs the groups in order d = 0,1,…,9. Within the group for MSD = d, the order is the input order if d is stable, and reversed if d is anti‑stable. Consequently the final sequence on T2 is:

• For d = 0,1,2,3,6,7,8,9 (anti‑stable):
  (10d+9,;10d+8,;\dots,;10d+0)
• For d = 4,5 (stable):
  (10d+0,;10d+1,;\dots,;10d+9)

Writing the 100 keys explicitly:

[ \begin{aligned} &09;08;07;06;05;04;03;02;01;00\ &19;18;17;16;15;14;13;12;11;10\ &29;28;27;26;25;24;23;22;21;20\ &39;38;37;36;35;34;33;32;31;30\ &40;41;42;43;44;45;46;47;48;49\ &50;51;52;53;54;55;56;57;58;59\ &69;68;67;66;65;64;63;62;61;60\ &79;78;77;76;75;74;73;72;71;70\ &89;88;87;86;85;84;83;82;81;80\ &99;98;97;96;95;94;93;92;91;90 \end{aligned} ]

\boxed{09;08;07;06;05;04;03;02;01;00;19;18;17;16;15;14;13;12;11;10;29;28;27;26;25;24;23;22;21;20;39;38;37;36;35;34;33;32;31;30;40;41;42;43;44;45;46;47;48;49;50;51;52;53;54;55;56;57;58;59;69;68;67;66;65;64;63;62;61;60;79;78;77;76;75;74;73;72;71;70;89;88;87;86;85;84;83;82;81;80;99;98;97;96;95;94;93;92;91;90}

This completes the proof. ∎

Notes

The independence of the first pass’s stability from the final order relies on the fact that all keys are distinct and the initial order is increasing. If the initial order were different, the final permutation would change accordingly, but the pattern of reversed/non‑reversed blocks for each tens digit would remain the same.