TAOCP 5.2.4 Exercise 10

We show that straight two-way merge sort (Algorithm S) can be implemented using a single sequentially allocated memory area of size \(N + \lceil N/2\rceil \le \lceil 3N/2\rceil\).

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.4: Sorting by Merging

Exercise 10. [25] (D. A. Bell.) Show that sequentially allocated straight two-way merging can be done with at most $\tfrac{3}{2}N$ memory locations, instead of $2N$ as in Algorithm S.

Verified: no
Solve time: 4m18s

Solution

We show that straight two-way merge sort (Algorithm S) can be implemented using a single sequentially allocated memory area of size (N + \lceil N/2\rceil \le \lceil 3N/2\rceil). For simplicity, assume (N) is even (the odd case requires only a trivial adjustment with (\lceil N/2\rceil)); then the memory size is exactly (3N/2).

Memory layout

Allocate a contiguous block of (M = 3N/2) locations. Define two logical arrays of length (N):

  • Array (X) occupies locations (1,2,\ldots,N).
  • Array (Y) occupies locations (N/2+1, N/2+2, \ldots, 3N/2).

The two arrays overlap on the (N/2) locations (N/2+1,\ldots,N). Initially the (N) records to be sorted are placed in (X).

Merge passes

We perform passes exactly as in Algorithm S: run length (p) starts at (1) and doubles each pass ((p=1,2,4,\ldots)). However, we alternate the direction of merging:

  • Odd passes ((p = 1, 4, 16, \ldots)): merge from (X) into (Y), processing runs from right to left.
  • Even passes ((p = 2, 8, 32, \ldots)): merge from (Y) into (X), processing runs from left to right.

Within a pass, the merging of one pair of runs of length (p) (except possibly the last run) is done by the standard straight two-way merge procedure (steps S3-S11 of Algorithm S), adapted to the current direction. The variables (i,j) point to the current elements of the two source runs, (k) points to the current destination position, and (q,r) count the remaining elements in the two runs. The only changes are the initialisation of (i,j,k) and the increment/decrement steps, which follow the chosen direction.

Correctness of the overlap

We must verify that no location in the overlap region is written before its value has been read from the source array.

Odd pass ((X \to Y), right‑to‑left).
The destination (Y) ends at (3N/2), which is outside (X). The write pointer (k) starts at the end of (Y) and moves left. The overlap region is (N/2+1,\ldots,N). The first (N/2) writes go to locations (3N/2, 3N/2-1, \ldots, N+1) - completely outside (X). Only after (N/2) writes does (k) enter the overlap region (at location (N)). At that moment exactly (N/2) elements have been read from the source (X). Since the source is read from right to left, the (N/2) elements read are precisely the last (N/2) elements of (X), i.e. the overlap region. Hence every location in the overlap has been read before it is overwritten.

More formally, let (j) be the read pointer for the right run of the current pair (the run that lies in the overlap when the pair is the rightmost one). Initially (k = 3N/2), (j = N), so (k - j = N/2). When an element is taken from the right run, both (k) and (j) decrease by (1) (difference unchanged). When an element is taken from the left run, (k) decreases by (1) while (j) stays (difference decreases by (1)). The total number of elements taken from left runs during the whole pass is exactly (N/2) (there are (N/(2p)) pairs, each left run has length (p)). Therefore (k - j) never becomes negative; i.e. (k \ge j) throughout. When (k) is in the overlap ((k \le N)), we have (k \ge j), so location (k) has either already been read ((k > j)) or is the current element to be read ((k = j)). In either case no unread data is destroyed.

Even pass ((Y \to X), left‑to‑right).
The destination (X) starts at (1), outside the overlap. The write pointer (k) starts at (1) and moves right. The first (N/2) writes go to (1,2,\ldots,N/2) - outside (Y). After (N/2) writes, (k) enters the overlap at (N/2+1). By then (N/2) elements have been read from the source (Y) in left‑to‑right order. The first (N/2) elements of (Y) are exactly the overlap region (N/2+1,\ldots,N). Thus again all overlapping locations have been read before being written.

A symmetric formal argument (using the read pointer for the left run) shows that the difference (\text{read_pointer} - k) stays non‑negative.

If a pass ends with an unpaired run (which happens when the number of runs is odd), that run is simply copied to the destination in the same direction as the merge; the same reasoning guarantees safety.

Final output

After the last pass the sorted sequence resides in either (X) or (Y). If it is in (Y) and the result is required in the original area (1\ldots N), we copy the first (N/2) elements of (Y) into (X); the remaining (N/2) elements of (Y) already occupy the correct locations (N/2+1\ldots N) because of the overlap. This final copy uses no extra memory.

Memory usage

The total memory used is (N + N/2 = 3N/2) locations for even (N). For odd (N) we take (\lceil N/2\rceil) locations for the overlap, giving (N + \lceil N/2\rceil \le \lceil 3N/2\rceil) locations. The number of passes and the asymptotic running time are identical to Algorithm S.

This completes the proof. ∎