TAOCP 5.4.1 Exercise 28
The key difficulty is not comparison but **storage lifetime**: a variable-length record must remain accessible through its descriptor for as long as it may still reside in the selection tree.
Section 5.4.1: Multiway Merging and Replacement Selection
Exercise 28. [25] [25] The text considers only the case that all records to be sorted have a fixed size. How can replacement selection be done reasonably well on variable-length records?
Verified: yes
Solve time: 3m49s
The key difficulty is not comparison but storage lifetime: a variable-length record must remain accessible through its descriptor for as long as it may still reside in the selection tree. This forces an explicit discipline for buffer reuse in external memory.
A correct implementation proceeds by keeping the usual replacement selection structure unchanged and solving only the storage management problem.
Each record $R$ is represented in the tournament tree by a fixed-size descriptor
$$ D(R) = \langle K(R), a(R) \rangle, $$
where $K(R)$ is the key and $a(R)$ is an address consisting of a block identifier and an offset (and optionally a length), so that the full record can be retrieved when needed.
The input is read into a buffer pool of disk blocks. Each block contains a sequence of packed variable-length records together with a local directory of offsets. This part is standard and does not by itself guarantee correctness; the essential point is how long a block is allowed to be reused.
The correction is to enforce the following invariant:
A block remains allocated in the buffer pool until no descriptor in the selection tree refers to any record stored in that block.
To maintain this invariant, each block $B$ stores a reference counter
$$ \mathrm{cnt}(B) = \text{number of heap elements whose record lies in } B. $$
When a record $R$ is read from a block $B$, the algorithm does the following. The record is located inside the input buffer, and a descriptor $D(R)$ containing a pointer to its position in $B$ is inserted into the tournament tree. At that moment, $\mathrm{cnt}(B)$ is incremented by 1.
Replacement selection proceeds exactly as in the fixed-length case. Whenever a record $R$ is selected as the current minimum and is output, the algorithm accesses it through its descriptor and writes it to the output run. Immediately after this extraction, the corresponding block counter is decremented:
$$ \mathrm{cnt}(B) \leftarrow \mathrm{cnt}(B) - 1. $$
Only when $\mathrm{cnt}(B) = 0$ may block $B$ be returned to the free pool and overwritten by a new input block.
This guarantees correctness because every descriptor in the tournament tree always points either to a still-resident block or to a block whose lifetime has been extended precisely because at least one of its records remains in the tree. No block is ever reused while any of its records may still be selected later.
It is important that “input consumption” and “buffer reuse” are decoupled. A block may have all of its records already inserted into the selection tree, yet it cannot be discarded until those records have been removed from the tree through output. Thus block recycling is driven by reference counts, not by scan position.
The rest of replacement selection is unchanged. The tournament tree stores only fixed-size descriptors, comparisons are performed solely on keys $K(R)$, and replacement after output proceeds by inserting the next input record as long as it does not violate the current run constraint.
An equivalent formulation is to say that variable-length records are supported by pinning input blocks in the buffer pool until all of their contained records have been expelled from the selection structure. This pinning is exactly what the reference counters enforce.
With this discipline, no dangling pointers arise, the heap operations remain identical to the fixed-size case, and the external-memory behavior of replacement selection is preserved.