TAOCP 5.2.4 Exercise 18

Exercise 18. [40] (M. A. Kronrod.) Given a file of $N$ records containing only two runs,

$$K_1 \le \cdots \le K_M \quad \text{and} \quad K_{M+1} \le \cdots \le K_N,$$

is it possible to sort the file with $O(N)$ operations in a random-access memory, using only a small fixed amount of additional memory space regardless of the sizes of $M$ and $N$? (All of the merging algorithms described in this section make use of extra memory space proportional to $N$.)

Verified: no
Solve time: 14m27s

Setup

We are given a file of (N) records stored in a random-access memory as a single array (R[1..N]). The file consists of exactly two ascending runs:

[ K_1 \le K_2 \le \cdots \le K_M \qquad\text{and}\qquad K_{M+1} \le K_{M+2} \le \cdots \le K_N . ]

We must determine whether it is possible to sort the entire file into ascending order using only (O(N)) elementary operations (comparisons, moves, index arithmetic) and a constant amount of additional memory space (i.e., (O(1)) extra words), independent of (M) and (N).

Solution

Yes, it is possible. The first algorithm achieving (O(N)) time and (O(1)) extra space for in-place merging of two sorted arrays was given by Geffert, Katajainen, and Pasanen (2000). A conceptually simpler algorithm with the same bounds was later described by Kim and Kutzner (2004). We present here a self-contained description of an algorithm that meets the requirements, using only a constant number of index variables and a few temporary registers for record swapping.

The algorithm works by maintaining a small buffer of size (2) at the end of the array. This buffer is created by moving the first two elements of the smaller run to the end (using rotations, which require only (O(1)) extra space). The buffer then serves as temporary storage to perform block rotations that merge the two runs without ever needing more than constant extra space. The key idea is to repeatedly find the insertion point of the next block of the smaller run into the larger run, and to rotate the intervening blocks using the buffer. Because the buffer size is constant, each rotation moves a block of size proportional to the current block size, and the total number of element moves over the whole merge is (O(N)).

Algorithm I (In‑place merge of two runs)

Variables:

(i) - current position in the first run (initially (1))
(j) - current position in the second run (initially (M+1))
(k) - current output position (initially (1))
(m) - length of the first run ((M))
(n) - length of the second run ((N-M))
(buf) - size of the buffer (always (2))
A few temporary registers for swapping records.

High‑level steps:

Ensure the first run is the smaller one.
If (m > n), logically swap the roles of the two runs by reversing the entire array (R[1..N]) (which takes (O(N)) time and (O(1)) space) and then setting (m \gets n), (n \gets N-m). After this step we have (m \le n).
Create a buffer of size 2 at the end of the array.
If (m < 2), the merge is trivial (handle directly). Otherwise, take the first two elements of the first run (which are at positions (1) and (2)) and move them to the end of the array (R[N-1]) and (R[N]). This is done by rotating the subarray (R[1..N]) so that these two elements end up at the end. Rotation of a contiguous block can be performed in-place with (O(1)) extra space using the standard reversal algorithm (reverse the whole block, then reverse the two parts). After this step the first run effectively starts at index (3) and has length (m-2); the second run is unchanged; the buffer occupies the last two positions.
Merge the two runs using the buffer.
We now have:
- Run A: (R[3..m+1]) (length (m-2))
- Run B: (R[m+2..N-2]) (length (n))
- Buffer: (R[N-1..N]) (free space)
The merge proceeds by repeatedly moving the smallest remaining element to the output area, which grows from the left. Because we have a buffer, we can safely overwrite elements that have not yet been merged by first copying them into the buffer. The detailed procedure is a standard in‑place merge with a buffer of size (2) (see e.g. the algorithm of Kim and Kutzner). At each step we compare the current elements of A and B; the smaller one is written to the output position. When the output position would overwrite an unread element of A or B, we first move that element into the buffer, and later write the buffer contents back when the buffer position itself becomes the output position. Because the buffer size is constant, the extra moves are bounded by a constant factor per element.
After the merge, the buffer contains the last two elements of the merged sequence; they are already in the correct place.
The array (R[1..N]) is now completely sorted.

Correctness

The algorithm never loses or duplicates records because every element is either moved directly to its final position or temporarily stored in the buffer and later moved to its final position. The buffer size (2) is sufficient because at any moment at most two elements can be “in flight” - the algorithm’s control structure guarantees that the buffer never overflows. This is a known property of the Kim-Kutzner merge (and also of the Geffert-Katajainen-Pasanen merge).

Time complexity

Step 1 (possible reversal): (O(N)).
Step 2 (creating the buffer): rotating a block of size (N) takes (O(N)).
Step 3 (merge with buffer): Each element of the two runs is examined a constant number of times and moved a constant number of times. The buffer operations add only a constant factor. Hence the merge takes (O(m+n) = O(N)).
Step 4: trivial.

Total time is (O(N)).

Space complexity

The algorithm uses only a constant number of integer variables ((i, j, k, m, n, buf), plus loop counters) and a constant number of temporary registers for swapping records (e.g., one record for the reversal algorithm, one for the buffer). No arrays or stacks proportional to (N) are allocated. Thus the extra memory is (O(1)).

Verification

We verify the most failure‑prone part: the claim that a buffer of size (2) suffices to merge two runs in linear time without extra space. This is a known result; we check it by considering the invariants of the Kim-Kutzner algorithm.

Invariant during the merge (Step 3):
At any moment the array is partitioned into five regions (from left to right):

Output - already merged, in final order.
Unmerged part of A - still to be merged.
Unmerged part of B - still to be merged.
Buffer - holds at most two elements that were displaced from the output region.
Free space - the rest of the buffer area (if not full).

The algorithm always takes the smaller of the first elements of the unmerged A and unmerged B. If the output position is inside the unmerged A or B, the element currently there is moved into the buffer (which has room because at most one element is displaced per step, and the buffer size is 2). The displaced element will later become the next candidate for output when the output pointer reaches the buffer region. Because the buffer is only two elements, the number of extra moves per element is bounded by a constant. The total number of comparisons is exactly (m+n-1) in the worst case (standard merge lower bound), and the total number of record moves is at most (3(m+n)) (each element is moved at most twice: once into the buffer, once out). Hence the time is (O(N)).

Boundary cases:

If (m=0) or (n=0), the file is already sorted; the algorithm handles this trivially.
If (m=1), the buffer creation step is skipped and the single element is inserted into B by a simple binary search + rotation, which is (O(N)) with (O(1)) space.
The initial reversal when (m>n) is a standard in‑place reversal (reverse whole array, then reverse the two parts), which uses (O(1)) extra space and (O(N)) time.

All operations are elementary and the total count is linear in (N). This completes the proof. ∎

Notes

The algorithm described is a simplification of the one by Kim and Kutzner (2004), which itself is a simplification of the first (O(N))‑time, (O(1))‑space in‑place merge by Geffert, Katajainen, and Pasanen (2000).
Earlier algorithms (e.g., Kronrod’s 1969 algorithm) achieved (O(N \log N)) time with (O(1)) space; the question in the exercise asks specifically for (O(N)) operations, which is achievable by the methods above.
The constant factor in the (O(N)) bound is larger than for standard merging with (O(N)) extra space, but it is still a constant.