TAOCP 5.2.4: Sorting by Merging
Section 5.2.4 exercises: 8/8 solved.
Section 5.2.4. Sorting by Merging
Exercises from TAOCP Volume 3 Section 5.2.4: 8/8 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | verified | 5m59s | |
| 2 | [**] | solved | 2m50s | |
| 3 | [**] | verified | 1m13s | |
| 4 | [**] | verified | 1m09s | |
| 5 | [21] | medium | verified | 1m15s |
| 6 | [22] | medium | verified | 1m14s |
| 7 | [M34] | math-hard | solved | 4m48s |
| 8 | [M24] | math-medium | solved | 4m11s |
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...