TAOCP 5 Exercise 3

Section 5: Introduction to Sorting

Exercise 3. [**] [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}, \dots, a_{1,1000}; a_{2,1}, \dots, a_{2,1000}; \dots; a_{1000,1000}$. How do you create a tape in which the

elements are stored by columns $a_{j,1}, a_{2,1}, \dots, a_{1000,1}, a_{1,2}, \dots, a_{1000,2}, \dots, a_{1000,1000}$ instead?

(Try to make less than a dozen passes over the data.)

Verified: yes
Solve time: 1m

Each input word $a_{i,j}$ is read in the given row-major order and assigned the column index $j$. During a single sequential scan, each record is routed to one of 1000 output tapes so that tape $T_j$ receives exactly the elements of column $j$ in increasing row order.

Read tape $\leftarrow$ input tape in row-major order

Compute $i \leftarrow \left\lceil k/1000 \right\rceil$, $j \leftarrow k - 1000(i-1)$ for each word position $k$

Write $a_{i,j} \leftarrow T_j$

After completion of the scan, each tape $T_j$ contains the sequence $a_{1,j}, a_{2,j}, \ldots, a_{1000,j}$ in correct order. The final output tape is produced by a sequential concatenation of the auxiliary tapes:

Output tape $\leftarrow T_1, T_2, \ldots, T_{1000}$

The first pass preserves row order within each column because the input is processed in increasing $i$ for fixed $j$ only after cycling through all columns, and the mapping assigns each element to exactly one tape without reordering within that tape. The second pass restores the required global order by reading tapes in increasing column index and writing their contents sequentially. This completes the construction. ∎