TAOCP 5.2.4 Exercise 16

Exercise 16. [20] Design a list merging algorithm like Algorithm L but based on three-way merging.

Verified: no
Solve time: 4m56s

Solution

We present Algorithm L3, a straight three-way merge sort for linked lists. It generalizes Algorithm L (which uses a binary counter) to a ternary counter, merging three runs at a time.

Data structures

Each record contains a KEY field and a LINK field.
Λ denotes the null pointer.
The input list is given by a pointer HEAD.
We maintain two arrays BIN1[0..K] and BIN2[0..K] where K = ⌊log₃ N⌋. Each entry is either Λ or points to the head of a sorted run of length exactly 3ⁱ. The runs are linked lists terminated by Λ.
A queue Q_RUNS (implemented as a linked list with head and tail pointers) is used in the final phase.

Subroutine: `MERGE3(A, B, C)`

Merges three sorted lists A, B, C (any may be Λ) into one sorted list.
Returns the head of the merged list.
Implementation: Use a dummy header node D. Maintain a tail pointer T initially D. While at least one of A, B, C is non‑Λ, find the smallest key among the current nodes, detach that node, append it to T (LINK(T) ← node; T ← node), and advance the corresponding list pointer. Finally set LINK(T) ← Λ and return LINK(D). This is a standard three‑way merge; its correctness follows directly from the fact that the input lists are sorted.

Algorithm L3

L1. [Initialize.]
Set K ← ⌊log₃ N⌋.
For i = 0 to K set BIN1[i] ← Λ, BIN2[i] ← Λ.
Set P ← HEAD.

L2. [End of input?]
If P = Λ, go to L5.

L3. [Detach next record.]
Set Q ← P, P ← LINK(P), LINK(Q) ← Λ.
(Now Q is a run of length 1 = 3⁰.)

L4. [Add run to ternary counter.]
Set i ← 0, R ← Q.
  L4a. If BIN1[i] = Λ, set BIN1[i] ← R, go to L2.
  L4b. If BIN2[i] = Λ, set BIN2[i] ← R, go to L2.
  L4c. Set R ← MERGE3(BIN1[i], BIN2[i], R).
    Set BIN1[i] ← Λ, BIN2[i] ← Λ.
    Set i ← i + 1.
    If i > K, set K ← K + 1 (extend arrays if necessary).
    Go to L4a.

L5. [Collect remaining runs.]
Create an empty queue Q_RUNS.
For i = 0 to K:
If BIN1[i] ≠ Λ, enqueue BIN1[i] into Q_RUNS.
If BIN2[i] ≠ Λ, enqueue BIN2[i] into Q_RUNS.

L6. [Final merge.]
While Q_RUNS contains more than one run:
  Dequeue up to three runs (if fewer than three, dequeue all).
  Let the dequeued runs be X, Y, Z (missing ones taken as Λ).
  Set R ← MERGE3(X, Y, Z).
  Enqueue R into Q_RUNS.

L7. [Output.]
The single run left in Q_RUNS is the sorted list.
Set HEAD ← that run.
Terminate.

Correctness proof

Invariant (after L2, before processing the next record):
After some prefix of the input has been processed, the runs stored in BIN1[i] and BIN2[i] (for all i) are sorted, have lengths exactly 3ⁱ, and are pairwise disjoint (they partition the processed records). Moreover, if the number of processed records is written in base 3, the digits are exactly the counts of runs in each bin (0, 1, or 2).

Initialization: Before any record is processed, all bins are empty; the invariant holds for 0 records.

Maintenance (steps L3-L4): Step L3 creates a run of length 1 = 3⁰. Step L4 adds this run to the ternary counter.

If BIN1[i] is empty, we store the run there (digit increases from 0 to 1).
Else if BIN2[i] is empty, we store the run there (digit increases from 1 to 2).
Else both slots are full (digit 2). We merge the three runs of length 3ⁱ into one run of length 3ⁱ⁺¹ (a carry), clear the bin, and repeat at level i+1.
This exactly mimics addition of 1 in base 3, preserving the invariant.

Termination of L4: Each iteration of L4 either stores the run (exiting to L2) or performs a carry to the next level. Since the total number of records is N, the carry chain can propagate at most ⌈log₃ N⌉ steps, so L4 always terminates.

After L2 finds P = Λ, the invariant holds for all N records. The bins contain a set of sorted runs whose lengths are powers of three, partitioning the entire input.

Final merge (L5-L6):
The queue Q_RUNS initially contains exactly these runs. Each iteration of L6 removes up to three runs and replaces them with their sorted merge (MERGE3). Because merging sorted lists produces a sorted list containing exactly the union of the elements, the queue always contains a partition of the original records into sorted runs. The number of runs decreases by at least one each iteration (3 → 1, 2 → 1, and the loop stops when only one run remains). Hence the loop terminates with a single run, which is a sorted list of all N records.

Thus Algorithm L3 correctly sorts the input list. ∎

Complexity

Each record is detached once (L3) and participates in O(log₃ N) merges.
The total number of key comparisons is the same as for straight three‑way merge sort: at most N⌈log₃ N⌉ - (3^{⌈log₃ N⌉} - 1)/2 + O(N).
Running time is O(N log N).
Extra space: O(log N) for the bin arrays and the queue.

Notes

The algorithm handles N = 0 (empty input) correctly: L2 immediately goes to L5, the queue stays empty, and L7 would find no run (but the problem assumes N ≥ 1; if N = 0 we can define the output as Λ).
MERGE3 gracefully accepts Λ arguments, so the final merge works uniformly even when the number of remaining runs is not a multiple of three.
If desired, the final merge can be done by cascading from the highest bin down, but the queue method uses only three‑way merges throughout and is simpler to describe.