TAOCP 5.2.4: Sorting by Merging
Section 5.2.4 exercises: 23/23 solved.
Section 5.2.4. Sorting by Merging
Exercises from TAOCP Volume 3 Section 5.2.4: 23/23 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [21] | medium | verified | 5m59s |
| 2 | [M24] | math-medium | solved | 2m50s |
| 3 | ▶ [20] | medium | verified | 1m13s |
| 4 | [21] | medium | verified | 1m09s |
| 5 | ▶ [21] | medium | verified | 1m15s |
| 6 | [22] | medium | verified | 1m14s |
| 7 | [16] | medium | solved | 4m48s |
| 8 | [22] | medium | solved | 4m11s |
| 9 | [24] | medium | solved | 12m38s |
| 10 | [25] | medium | solved | 4m18s |
| 11 | [21] | medium | solved | 2m14s |
| 12 | ▶ [22] | medium | solved | 8m13s |
| 13 | ▶ [M32] | math-hard | solved | 17m43s |
| 14 | [M24] | math-medium | solved | 7m45s |
| 15 | [20] | medium | solved | 2m51s |
| 16 | [20] | medium | solved | 4m56s |
| 17 | [20] | medium | solved | 2m47s |
| 18 | [40] | project | solved | 14m27s |
| 19 | [26] | hard | solved | 23m50s |
| 20 | [47] | research | solved | 7m42s |
| 21 | [22] | medium | solved | 4m06s |
| 22 | [28] | hard | solved | 10m27s |
| 23 | [M30] | math-hard | solved | 2m45s |
TAOCP 5.2.4 Exercise 1
**Corrected Solution to Exercise 5.
TAOCP 5.2.4 Exercise 2
Let $X$ be the number of times step M2 is executed when merging $x_1,\dots,x_m$ with $y_1,\dots,y_n$.
TAOCP 5.2.4 Exercise 3
The modification introduces an additional equality case in the comparison step of Algorithm M so that records from the first file are omitted whenever their keys also occur in the second file.
TAOCP 5.2.4 Exercise 4
Let the records be stored in three contiguous segments of $N$ locations each, denoted $A_1,\ldots,A_N$, $B_1,\ldots,B_N$, and $C_1,\ldots,C_N$.
TAOCP 5.2.4 Exercise 5
A sorting method is stable if whenever two records $R_a$ and $R_b$ satisfy $K_a = K_b$ and $R_a$ precedes $R_b$ in the input, then $R_a$ precedes $R_b$ in the output.
TAOCP 5.2.4 Exercise 6
Let Algorithm L be the straight two-way merge sort in which the initial step L1 sets the system so that every record $R_i$ forms a run of length $1$, and later steps repeatedly merge runs of fixed siz...
TAOCP 5.2.4 Exercise 7
A correct analysis must stay inside the structural model of Program L (natural two-way merge on runs), interpret the quantities exactly as defined in Knuth’s framework, and then specialize to the conc...
TAOCP 5.2.4 Exercise 8
The error in the previous solution occurs at exactly one decisive point: the computation of m_k=\left\lfloor \frac{r_k}{2}\right\rfloor from the binary expansion of $N$.
TAOCP 5.2.4 Exercise 9
**Register assignment** rI1 = i (left source pointer) rI2 = j (right source pointer) rI3 = k (destination pointer) rI5 = q (elements left in current left run) rI6 = r (elements left in current right r...
TAOCP 5.2.4 Exercise 10
We show that straight two-way merge sort (Algorithm S) can be implemented using a single sequentially allocated memory area of size \(N + \lceil N/2\rceil \le \lceil 3N/2\rceil\).
TAOCP 5.2.4 Exercise 11
Algorithm L (List merge sort) is a stable sorting method.
TAOCP 5.2.4 Exercise 12
We revise step L1 of Algorithm L (List merge sort) as follows.
TAOCP 5.2.4 Exercise 13
Program L is the MIX implementation of Algorithm S (straight two-way merge sort) from Section 5.
TAOCP 5.2.4 Exercise 14
Algorithm L is the straight two-way merge sort described in the text.
TAOCP 5.2.4 Exercise 15
The redundancy occurs in the main merge loop of Algorithm L.
TAOCP 5.2.4 Exercise 16
We present **Algorithm L3**, a straight three-way merge sort for linked lists.
TAOCP 5.2.4 Exercise 17
We maintain the invariant that the $N$ records are distributed among a set of stacks (or lists) $S_0, S_1, S_2, \ldots$, where each stack $S_k$ either is empty or contains exactly one sorted run (subf...
TAOCP 5.2.4 Exercise 18
We are given a file of \(N\) records stored in a random-access memory as a single array \(R[1.
TAOCP 5.2.4 Exercise 19
We consider the railway switching network with \(n\) stacks as depicted in Fig.
TAOCP 5.2.4 Exercise 20
We consider the railway network with $n$ stacks in parallel shown in Fig.
TAOCP 5.2.4 Exercise 21
We modify Algorithm L (List merge sort) as follows.
TAOCP 5.2.4 Exercise 22
We consider the problem of sorting \(N\) records \(R_1,\dots,R_N\) whose keys are **multiword**: each key \(K_i\) consists of \(W\) words \[ K_i = (K_i[1], K_i[2], \dots, K_i[W]), \] where \(K_i[1]\)...
TAOCP 5.2.4 Exercise 23
The top-down (divide-and-conquer) merge sort splits a file of \(N\) records into two subfiles of sizes \(\lceil N/2\rceil\) and \(\lfloor N/2\rfloor\), sorts them recursively, and merges the results.