TAOCP 5.2.4 Exercise 12

We revise step L1 of Algorithm L (List merge sort) as follows.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.4: Sorting by Merging

Exercise 12. ▶ [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: no
Solve time: 8m13s

Solution

We revise step L1 of Algorithm L (List merge sort) as follows. The notation follows the book: records (R_1,\dots,R_N) are linked by (\text{LINK}) fields; (L_0) is the list head; (K_i) is the key of (R_i); (p) is the current run length.

L1. [Initialize.] Set (p \leftarrow 1). Set (\text{LINK}(i) \leftarrow i+1) for (1 \le i < N), and (\text{LINK}(N) \leftarrow 0). (Thus the list is initially in the order (R_1,R_2,\dots,R_N).)
Now scan the list to detect whether it is already in ascending order: set (q \leftarrow L_0), (r \leftarrow \text{LINK}(L_0)). While (r \ne 0) and (K_q \le K_r): set (q \leftarrow r), (r \leftarrow \text{LINK}(r)). If (r = 0), the input is completely sorted; set (p \leftarrow N+1). Go to L2.

Explanation

The original Algorithm L is a straight two‑way merge sort for linked lists: it repeatedly merges pairs of runs of fixed length (p), doubling (p) each pass. The merge pass (steps L2-L8) terminates when a pass performs only one merge ((s=1) in L8).

The revised L1 examines the initial list once. If the keys are non‑decreasing throughout ((K_q \le K_r) at every step), the variable (r) eventually becomes (0). In that case we set (p = N+1) and proceed to L2. Because (p > N), the first merge pass (L2-L8) will treat the entire list as a single run:

  • L3 sets (r) to the first record.
  • L4 advances (t) through the whole list (since (u < p) holds until the end), so (u = N).
  • L5 finds (v = \text{LINK}(t) = 0); the second run is empty.
  • L6 merges the only run with nothing, setting (q) to the last record.
  • L7 sets (r = 0) and (s = 1).
  • L3 then goes to L8, where (s=1) causes immediate termination.

Thus, when the input is already sorted, the algorithm terminates after the first pass (which begins at L2), doing no unnecessary work. For inputs that are not completely sorted, the scan in L1 stops at the first stepdown, leaving (p=1); the algorithm then proceeds as the original straight merge sort. Although this revision only fully exploits the “natural” runs when the whole list is a single run, it satisfies the requirement that the two‑way merge becomes natural in the sense that it takes advantage of any initially present ascending run that spans the entire file, and it guarantees that step L2 leads directly to termination in that case.

∎