TAOCP 5 Exercise 10

Section 5: Introduction to Sorting

Exercise 10. [15] You are given a tape containing one million words of data. How do you determine how many distinct words are present on the tape?

Verified: yes
Solve time: 10m07s

Solution

We are given a tape containing (N = 10^6) words and have at most a few thousand words of internal memory (say (M) words, where (M \ll N)) and about six tape units. The goal is to count the number of distinct words on the tape.

Because the number of distinct words may be as large as (N) and internal memory is too small to hold a hash table or any other direct summary of all distinct values, the standard method is to sort the tape externally and then count the distinct words in one sequential scan of the sorted output. The steps are as follows.

1. External merge sort

Let the available tape units be (T_0, T_1, \dots, T_{k-1}) with (k \approx 6). We use (T_0) as the input tape and the others as working tapes. The internal memory can hold (B) words (e.g., (B = 2000)).

• Run formation:
  Repeatedly read (B) words from (T_0) into memory, sort them internally (e.g., with quicksort or heapsort), and write the sorted block (a run) to the working tapes in round‑robin fashion. After this phase, the data is distributed as sorted runs across the working tapes.

• Merge passes:
  Perform balanced multiway merges. In each pass, read one run from each of (k-1) input tapes, merge them in memory using a (k-1)-way merge (a priority queue of size (k-1) suffices), and write the merged run to the output tape. Alternate the roles of the tapes so that after each pass the number of runs decreases by a factor of (k-1).
  Repeat until only one run remains on one tape. This final tape contains all (N) words in non‑decreasing order.

The sorting requires (O(N \log N)) time and uses only the provided tape units; internal memory never holds more than (B + O(k)) words.

2. Counting distinct words

After sorting, make one sequential pass over the final sorted tape:

1. Set (\text{count} = 0) and (\text{prev} = \text{null}).
2. For each word (w) read from the tape:
   • If (w \neq \text{prev}) (or this is the first word), increment (\text{count}) and set (\text{prev} = w).
3. Output (\text{count}).

Because equal words are adjacent in the sorted order, (\text{count}) equals exactly the number of distinct words on the original tape.

Correctness argument

• Invariant of the merge sort: After each merge pass, every run on every tape is sorted, and the multiset of all words on all tapes is exactly the original multiset.
• Termination: The number of runs decreases geometrically; since (N) is finite, after (\to (1) run in (\lceil \log_{k-1}(N/B) \rceil) passes.
• Counting invariant: During the final scan, after processing the first (i) words of the sorted tape, (\text{count}) equals the number of distinct values among those (i) words, and (\text{prev}) is the value of the last word processed. This holds trivially initially and is preserved because the sorted order groups equal words together.
• Final value: When all (N) words are processed, (\text{count}) is the number of distinct words in the entire file.

Complexity

• Time: The sort dominates with (O(N \log N)) comparisons and tape I/O operations. The final scan is (O(N)).
• Space: (O(N)) words on tape; (O(B)) words in memory.

This method works for any (N) and any key type that can be compared, and it meets the constraint of limited internal memory and a handful of tape units. ∎

Notes

If the number of distinct words were known to be small enough to fit in internal memory, a hash table could be built in one pass without sorting. However, the problem statement gives no such guarantee, so the sorting‑based method is the general solution. The same algorithm is optimal for external sorting: (\Theta(N \log N)) is the minimum number of comparisons needed when only pairwise key comparisons are used.