TAOCP 5 Exercise 13

Exercise 13. [M26] How could you "shuffle" a large file of $N$ words into a random rearrangement?

Verified: yes
Solve time: 8m32s

Setup

We are given a file of (N) words (records) (R_1, R_2, \ldots, R_N) stored on external storage (e.g., magnetic tape). Each record contains a key field and satellite data; the goal is to rearrange the records into a uniformly random permutation. We assume access to a source of independent random bits and the ability to perform external sorting (e.g., balanced merge sort) using a stable sorting algorithm.

Solution

To shuffle the file we use the following algorithm based on sorting by random keys:

Key generation. Read the input file sequentially. For each record (R_j) ((1 \le j \le N)), generate a random key (K_j) drawn independently from a continuous uniform distribution on ([0,1]) (or, in practice, from a sufficiently large discrete set such as ({0,1,\ldots,2^{64}-1})). Write the pair ((K_j, R_j)) to a temporary file.
External sort. Sort the temporary file of ((K_j, R_j)) pairs by the key (K_j) using a stable external sorting algorithm (e.g., balanced two-way merge sort). Stability ensures that if two keys are equal (a probability-zero event for continuous keys, or a rare event for discrete keys), the original relative order of the corresponding records is preserved.
Output. Read the sorted file sequentially, discard the keys, and write the records (R_j) to the output file in the order they appear.

Proof of uniformity.
Let the original records be (R_1, R_2, \ldots, R_N). The random keys (K_1, K_2, \ldots, K_N) are independent and identically distributed. Since the distribution is continuous, (\Pr(K_i = K_j) = 0) for all (i \ne j); hence with probability (1) all keys are distinct. The sorting step produces a permutation (p) of ({1,\ldots,N}) such that [ K_{p(1)} < K_{p(2)} < \cdots < K_{p(N)}. ] The joint density of ((K_1,\ldots,K_N)) is symmetric under any permutation of the indices: for any permutation (\pi), [ f(K_{\pi(1)},\ldots,K_{\pi(N)}) = f(K_1,\ldots,K_N). ] Consequently, the event that the sorted order equals a given permutation (\pi) has the same probability for all (\pi). Since there are (N!) permutations and the events are disjoint and exhaustive (up to a set of measure zero), each occurs with probability (1/N!). Thus the output order (R_{p(1)}, \ldots, R_{p(N)}) is uniformly distributed over all (N!) rearrangements.

Practical considerations for discrete keys.
When keys are drawn from a finite set of size (M) (e.g., (M = 2^{64})), ties can occur. To maintain exact uniformity, we can adopt one of the following strategies:

Use a stable sort and generate a secondary independent random key for every record. If a tie occurs on the primary key, the secondary key breaks it. By iterating this process (or by using a key space large enough that the probability of a tie on all keys is negligible), we achieve exact uniformity.
Alternatively, detect ties during the sort (adjacent equal keys after sorting). For each group of records with equal keys, recursively apply the same shuffling procedure to that group (using fresh random keys). This resolves ties without bias because the recursive shuffle is independent and uniform on the subset.

The external sort requires (O(\log N)) passes over the data when using a balanced merge sort. The total time is (O(N \log N)), which is optimal for comparison-based methods.

Verification

We verify the correctness of the uniformity proof and the tie-handling strategy by examining the most failure-prone aspects: the discrete-key case and the boundary (N=1).

Uniformity with discrete keys and stable sort.
Suppose we use a stable sort and draw keys independently from a finite set ({1,\ldots,M}). Let the keys be (K_1,\ldots,K_N). The stable sort produces a permutation (p) such that (K_{p(1)} \le K_{p(2)} \le \cdots \le K_{p(N)}), with ties resolved by original order. Is the distribution of (p) uniform? No, it is not. For example, take (N=2), (M=2). The possible key pairs ((K_1,K_2)) are ((1,1),(1,2),(2,1),(2,2)), each with probability (1/4). The stable sort yields:

((1,1) \to) order ((1,2)) (original order)
((1,2) \to) order ((1,2))
((2,1) \to) order ((2,1))
((2,2) \to) order ((1,2)) Thus (\Pr(p = \text{id}) = 3/4), (\Pr(p = (1;2)) = 1/4), which is not uniform. This confirms that a stable sort alone does not produce a uniform permutation when ties are possible.

Tie-breaking by secondary key.
If we append an independent secondary key (L_j \in {1,\ldots,M}) and sort by ((K_j, L_j)) lexicographically (with stable sort on the composite key), the probability of a tie on both keys is (1/M^2). For (M=2^{64}), this is astronomically small. More rigorously, we can resolve ties by repeatedly generating fresh random keys for the tied records until all keys in the group are distinct; since the number of records is finite and the key space is positive, this process terminates with probability (1) and yields a uniformly random permutation of the tied group, independent of the rest. By induction on group size, the overall permutation is uniform.

Boundary case (N=1).
The algorithm generates a key for the single record, sorts (trivial), and outputs the record. The only permutation is the identity, which is trivially uniform.

Independent check: Random merge alternative.
Another known method is the random merge shuffle: recursively split the file into two subfiles by independent coin flips, shuffle each subfile, then merge by at each step choosing the next record from the first subfile with probability proportional to its current size. This also yields a uniform permutation and uses (O(N \log N)) time with (O(\log N)) passes, but it does not require generating and storing keys for all records simultaneously. The uniformity follows from the fact that the splitting and merging probabilities correspond exactly to the distribution of a uniformly random binary tree (or to the random permutation generated by the "random merge" construction). This provides an independent algorithm achieving the same goal, confirming that the problem is well-posed and the random-key sort is not the only solution.

This completes the verification. ∎

Notes

The random-key sort method is the standard way to shuffle a large file when an external sort routine is available. It reduces the problem of random permutation to the well-studied problem of sorting. The exercise's rating M26 reflects the need to prove uniformity rigorously and to address the subtlety of ties in finite-precision implementations.