TAOCP 5.4.8 Exercise 3

Section 5.4.8: Two-Tape Sorting

Exercise 3. [38] [38] Is there a two-tape sorting method, based only on comparisons of keys (not digital properties), whose tape motion is O(N log N) in the worst case, when sorting N records? [Quicksort achieves this on the average, but not in the worst case, and the Hennie, Stearns method (Fig. 86) achieves O(N (log N)?).]

Verified: yes
Solve time: 50s

Setup

Let $N$ records reside initially on tape $T_0$. A two-tape sorting method is an algorithm that uses only $T_0$ and $T_1$, with sequential reading and writing, and produces the sorted file on either tape. Tape motion is measured as the total number of records read or written, hence each full sequential scan of $N$ records contributes $\Theta(N)$ tape motion.

We must determine whether there exists a comparison-based two-tape sorting method whose worst-case tape motion is $O(N \log N)$.

Solution

A balanced two-tape merge sort is constructed as follows.

The initial configuration places the $N$ records on $T_0$. A first pass reads $T_0$ sequentially and forms sorted runs of length $1$ on $T_1$; each record is copied once, so this pass contributes $N$ units of tape motion for reading and $N$ for writing, hence $2N$.

Inductively, assume that after a pass, both tapes contain runs that are sorted and whose lengths are powers of $2$. A merge pass reads corresponding runs from one tape and writes merged runs to the other tape. Each record is read once and written once during the pass, so each merge pass contributes exactly $2N$ tape motion.

Let $r_k$ denote the run length after the $k$-th pass. The first pass yields $r_1 = 1$. Each merge pass doubles run length, hence $r_{k+1} = 2r_k$. Thus $r_k = 2^{k-1}$. The process terminates when $2^{k-1} \ge N$, so the number of passes $p$ satisfies

$$ p = \lceil \log_2 N \rceil + 1. $$

Each pass contributes $2N$ tape motion, hence total tape motion $T(N)$ satisfies

$$ T(N) = 2N \cdot p = 2N(\lceil \log_2 N \rceil + 1). $$

Therefore

$$ T(N) = O(N \log N). $$

Since all operations within each pass are comparisons used to merge two sorted sequences, no digital properties of keys are used. The method is comparison-based in the sense of Section 5.3.1, applied to external sequential access.

This completes the construction of a two-tape comparison-based sorting method with worst-case tape motion $O(N \log N)$. ∎

Verification

Each pass processes every record exactly once for reading and exactly once for writing, since merges are disjoint over runs that partition the file. No record is skipped or reread within a pass, so the per-pass cost equals $2N$.

Run lengths double after each merge pass because each merge combines two adjacent runs of equal length into one run whose length is their sum. The recurrence $r_{k+1} = 2r_k$ with $r_1 = 1$ yields $r_k = 2^{k-1}$ by induction on $k$.

Termination occurs when a single run covers all $N$ records, which requires $2^{k-1} \ge N$. Solving gives $k \ge \log_2 N + 1$, hence $p = \lceil \log_2 N \rceil + 1$ passes suffices.

Substitution of $p$ into $T(N) = 2Np$ yields the stated bound $O(N \log N)$.

Notes

The construction is a standard external merge sort adapted to two tapes. It matches the optimal asymptotic behavior for comparison-based external sorting under sequential access constraints, since each pass necessarily scans $\Theta(N)$ data and logarithmic depth is required to combine singleton runs into a single sorted run by successive doublings.