TAOCP 5 Exercise 12

We are given a magnetic tape containing \(10^6\) words representing a \(1000 \times 1000\) matrix in row-major order: \[ a_{1,1}, a_{1,2}, \dots, a_{1,1000},\; a_{2,1}, \dots, a_{2,1000},\; \dots,\; a...

taocpmathematicsalgorithmsvolume-3math-medium

Section 5: Introduction to Sorting

Exercise 12. [M25] (Transposing a matrix.) You are given a magnetic tape containing one million words, representing the elements of a $1000 \times 1000$ matrix stored in order by rows: $a_{1,1}, a_{1,2}, \ldots, a_{1,1000}, a_{2,1}, \ldots, a_{2,1000}, \ldots, a_{1000,1000}$. How do you create a tape in which the

elements are stored by columns $a_{1,1} a_{2,1} \ldots a_{100,1} a_{1,2} \ldots a_{100,2} \ldots a_{100,100}$ instead? (Try to make less than a dozen passes over the data.)

Verified: yes
Solve time: 19m11s

Solution

We are given a magnetic tape containing (10^6) words representing a (1000 \times 1000) matrix in row-major order: [ a_{1,1}, a_{1,2}, \dots, a_{1,1000},; a_{2,1}, \dots, a_{2,1000},; \dots,; a_{1000,1}, \dots, a_{1000,1000}. ] We have about six tape units and a few thousand words of high-speed internal memory. The task is to produce a tape with the elements in column-major order [ a_{1,1}, a_{2,1}, \dots, a_{1000,1},; a_{1,2}, \dots, a_{1000,2},; \dots,; a_{1,1000}, \dots, a_{1000,1000}, ] using fewer than twelve passes over the data.

Key construction.
Assign to each element (a_{i,j}) the integer key [ K = 1000(j-1) + (i-1), \qquad 1 \le i,j \le 1000. ] The keys range from (0) to (999,999) and are all distinct. In column-major order the element with key (K) is immediately followed by the element with key (K+1). Hence sorting the records by (K) yields exactly the desired permutation.

Algorithm: balanced three-way merge sort on six tapes.
Let the input tape be (T_0); the other five tapes are (T_1,\dots,T_5). The internal memory holds (M) words. We will store each record as a (key, value) pair, so we can process blocks of (B = \lfloor M/2 \rfloor) records at a time. Since (M) is “a few thousand”, we have (B \ge 1000) (in fact (B \ge 1500) if (M \ge 3000)).

Pass 1 - Run generation.
Read (T_0) sequentially. Maintain counters (i) (row) and (j) (column), initially (i=j=1). Repeatedly read a block of up to (B) elements from (T_0). For each element, compute its key (K = 1000(j-1)+(i-1)), then advance (j) (and increment (i) when (j) wraps from (1000) to (1)). Sort the (B) pairs ((K,\text{value})) internally by (K). Write the sorted block as one run to the tapes (T_1, T_2, T_3) in round-robin fashion. This pass reads the input once and writes all records to (T_1,T_2,T_3); it constitutes one pass over the data. The number of runs created is [ R = \left\lceil \frac{1,000,000}{B} \right\rceil \le 1000. ]

Merge passes.
We now have three tapes containing runs ((T_1,T_2,T_3)) and three empty tapes ((T_4,T_5,T_0)). Perform balanced three-way merges:

  • Merge the runs from the three input tapes into longer runs, writing them cyclically to the three output tapes.
  • After each merge pass, swap the roles of the input and output tape sets.

Each merge pass reads every record once from the input tapes and writes every record once to the output tapes, hence counts as one pass. The number of runs is divided by approximately (3) each pass. Starting with (R) runs, the number of merge passes required to obtain a single run is [ k = \lceil \log_3 R \rceil. ] Since (R \le 1000) and (3^6 = 729 < 1000 \le 2187 = 3^7), we have (k \le 7).

Final output.
After the last merge pass the sorted (key, value) pairs reside on one tape. During this final merge pass we simply write only the values (discarding the keys) to the desired output tape, so no extra pass is needed.

Total passes.
(1 + k \le 1 + 7 = 8) passes, which is well under the required dozen.

Verification of the worst case.
If (B = 1000) then (R = 1000). The merge passes reduce the run count as follows: [ 1000 \to 334 \to 112 \to 38 \to 13 \to 5 \to 2 \to 1, ] which indeed takes (7) merge passes. Total passes (= 8).

Correctness.
The key (K) is a strictly increasing function of the column-major index: if ((i_1,j_1)) precedes ((i_2,j_2)) in column-major order then (K_1 < K_2). Therefore sorting by (K) produces exactly the desired permutation. The balanced three-way merge sort is a correct sorting algorithm; it terminates because each pass reduces the total number of runs, and it maintains the invariant that all runs on the input tapes are sorted. This completes the proof. ∎

Remark.
If replacement selection is used instead of internal sorting for run generation, the average run length becomes (2B), reducing (R) to about (500) and the total passes to (7). Even with the simplest internal sort, the requirement of fewer than twelve passes is comfortably met.

\boxed{\text{The matrix transpose can be achieved in at most 8 passes using a balanced 3-way merge sort on 6 tapes with internal run generation.}}