TAOCP 5.2.4 Exercise 6

Section 5.2.4: Sorting by Merging

Exercise 6. [22] [22] Revise step L1 of Algorithm L so that the two-way merge is “natural,” taking advantage of ascending runs that are initially present. (In particular, if the input is already sorted, step L2 should terminate the algorithm immediately after your step L1 has acted.)

Verified: yes
Solve time: 1m14s

Solution

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 size.

The required modification replaces this artificial initialization by a decomposition of the input into maximal ascending runs, while preserving the interface expected by step L2.

In the revised step L1, the file $R_1,\ldots,R_N$ is scanned once from left to right. A run is defined as a maximal interval $R_a,\ldots,R_b$ such that $K_a \le K_{a+1} \le \cdots \le K_b$ and either $b=N$ or $K_b > K_{b+1}$. The scan begins with $a=1$ and repeatedly advances $b$ until a strict decrease $K_b > K_{b+1}$ is encountered or $b=N$. At each such position $b$, the pair $(a,b)$ is recorded as one initial run, and the next run begins at $a \leftarrow b+1$.

If during this scan no index $b$ is found with $K_b > K_{b+1}$, then the input consists of a single ascending run $R_1,\ldots,R_N$. In that case the modification sets a completion flag so that step L2 immediately recognizes termination and the algorithm halts after L1 has acted.

When more than one run is found, each run boundary replaces the implicit unit-length segmentation used in the original Algorithm L. The subsequent execution of L2 proceeds exactly as before, except that its initial list of runs is the sequence of maximal ascending runs produced by L1 rather than the sequence of single records.

This completes the proof. ∎