TAOCP 5 Exercise 11

Section 5: Introduction to Sorting

Exercise 11. [18] You are the U. S. Internal Revenue Service; you receive millions of "information" forms from organizations telling how much income they have paid to people, and millions of "tax" forms from people telling how much income they have been paid. How do you catch people who don't report all of their income?

Verified: yes
Solve time: 14m32s

Solution

We are given two large files:

• Information returns: each record is a pair $(id, amount)$ where $id$ identifies the payee and $amount$ is the payment reported by the payer.
• Tax returns: each record is a pair $(id, income)$ where $id$ identifies the taxpayer and $income$ is the total income reported by that taxpayer.

We must identify every $id$ for which the sum of $amount$ over all information returns with that $id$ exceeds the $income$ reported on the tax return for that $id$ (or for which no tax return exists).

Because the files contain millions of records and only a few thousand words of high‑speed memory are available, we use external sorting on the half‑dozen tape units. A balanced multiway merge sort is the standard method.

Algorithm

1. Sort the information returns by $id$ using an external merge sort. Write the sorted file to tape.
2. Sort the tax returns by $id$ using an external merge sort. Write the sorted file to tape.
3. Merge the two sorted files to detect discrepancies:
   • Position each file at its first record.
   • While either file has unprocessed records:
     • Let $id_I$ be the $id$ of the current information record, or $\infty$ if the file is exhausted.
     • Let $id_T$ be the $id$ of the current tax record, or $\infty$ if the file is exhausted.
     • Case $id_I < id_T$:
       The taxpayer $id_I$ has information returns but no tax return (all tax returns with smaller $id$ have already been processed). Accumulate the sum $S$ of $amount$ for all consecutive information records with this $id$. Output $id_I$ as a discrepancy (unreported income $S$). Advance the information file past all records with $id_I$.
     • Case $id_I = id_T$:
       Accumulate the sum $S$ of $amount$ for all consecutive information records with this $id$. Read the tax record(s) for this $id$ (normally there is exactly one; if multiple exist, sum their $income$ values to obtain $I$). If $S > I$, output $id_I$ as a discrepancy. Advance both files past all records with this $id$.
     • Case $id_I > id_T$:
       The taxpayer $id_T$ filed a tax return but has no information returns (or they have all been processed). This is not an underreporting discrepancy. Advance the tax file past all records with this $id$.

The output list contains precisely those taxpayers who failed to report all income shown on information returns.

Correctness

After sorting, all records for a given $id$ are contiguous in each file. The merge processes each distinct $id$ exactly once, in increasing order. For each $id$ it computes $S = \sum amount$ (payer‑reported total) and $I = \sum income$ (taxpayer‑reported total, taken as $0$ if no tax return exists). By construction, a discrepancy is reported exactly when $S > I$, which is the condition for underreporting.

Complexity

Let $N_I$ and $N_T$ be the number of information and tax returns, and let $N = \max(N_I, N_T)$. External merge sort on $k \ge 3$ tapes requires $O(N \log N)$ time and $O(N \log N)$ tape I/O, using only $O(1)$ internal memory besides I/O buffers. The final merge pass is linear. The total work is therefore $O(N \log N)$.

Boundary cases

• Multiple information returns per taxpayer: summed correctly.
• No tax return for a taxpayer with information returns: detected as $id_I < id_T$ with $I = 0$.
• Multiple tax returns per taxpayer: summed to $I$ before comparison.
• Taxpayer with tax return but no information returns: $id_I > id_T$; not an underreporting discrepancy.

This completes the proof. ∎

Notes

The same method works if the information returns contain payer identifiers and we wish to verify payer deductions; one simply sorts by payer $id$ instead of payee $id$. The algorithm is essentially the “coordinated merge” of two sorted files, a classic application of sorting to data reconciliation.