TAOCP 5 Exercise 5
Let each catalog card be considered as a record $R_j$ with a key $K_j$ that reflects the text of the card, including author, title, and date information.
Section 5: Introduction to Sorting
Exercise 5. [83] [83] (Library card sorting.) Before the days of computerized databases, every library maintained a catalog of cards so that users could find the books they wanted. But the task of putting catalog cards into an order convenient for human use turned out to be quite complicated as library collections grew. The following “alphabetical” listing indicates many of the procedures recommended in the American Library Association Rules for Filing Catalog Cards (Chicago: 1942):
| Text of card | Remarks |
|---|---|
| R. Accademia nazionale dei Lincei, Rome | Ignore foreign royalty (except British) |
| 1812; ein historischer Roman. Achtzehnhundertzwéolf | Bibliotheque d’histoire révolutionnaire. Treat apostrophe as space in French |
| Bibliotheque des curiosités. | Ignore accents on letters |
| Brown, Mrs. J. Crosby | Ignore designation of rank |
| Brown, John | Names with dates follow those without |
| Brown, John, mathematician | ... and the latter are subarranged by descriptive words |
| Brown, John, of Boston | |
| Brown, John, 1715-1766 | Arrange identical names by birthdate |
| BROWN, JOHN, 1715-1766 | Works “about” follow works “by” |
| Brown, John, d. 1811 | Sometimes birthdate must be estimated |
| Brown, Dr. John, 1810-1882 | Ignore designation of rank |
| Brown-Williams, Reginald Makepeace | Treat hyphen as space |
| Brown America. | Book titles follow compound names |
| Brown & Dallison’s Nevada directory. | & in English becomes “and” |
| Brownjohn, Alan | |
| Den’, Vladimir Eduardovich, 1867, | Ignore apostrophe in names |
| The den. | Ignore an initial article |
| Den lieben langen Tag. | ... provided it’s in nominative case |
| Dix, Morgan, 1827-1908 | Names precede words |
| 1812 ouverture. | Dix-huit cent douze |
| Le XIXe siécle frangais. | Dix-neuviéme |
| The 1847 issue of U. S. stamps. | Eighteen forty-seven |
| 1812 overture. | Eighteen twelve |
I am a mathematician. (a book by Norbert Wiener)
| Text of card | Remarks |
|---|---|
| IBM journal of research and development. | Initials are like one-letter words |
| ha-I ha-ehad. | Ignore initial article |
| Ia; a love story. | Ignore punctuation in titles |
| International Business Machines Corporation | |
| al-Khuwarizmi, Muhammad ibn Musa, fl. 813-846 | Ignore initial “al-” in Arabic names |
| Labour. A magazine for all workers. | Respell it “Labor” |
| Labor research association | |
| Labour, see Labor | Cross-reference card |
| McCall’s cookbook | Ignore apostrophe in English |
| McCarthy, John, 1927, | Mc = Mac |
| Machine-independent computer programming. | Treat hyphen as space |
| MacMahon, Maj. Percy Alexander, 1854-1929 | Ignore designation of rank |
| Mrs. Dalloway. | “Mrs.” = “Mistress” |
| Mistress of mistresses. | |
| Royal society of London | Don’t ignore British royalty |
| St. Petersburger Zeitung. | “St.” = “Saint”, even in German |
| Saint-Saëns, Camille, 1835-1921 | Treat hyphen as space |
| Ste-Marie, Gaston P | Sainte |
| Seminumerical algorithms. (a book by Donald Ervin Knuth) | |
| Uncle Tom’s cabin. (a book by Harriet Beecher Stowe) | |
| U.S. bureau of the census. | “U.S.” = “United States” |
| Vandermonde, Alexandre Théophile, 1735-1796 | |
| Van Valkenburg, Mac Elwyn, 1921- | Ignore space after prefix in surnames |
| Von Neumann, John, 1903-1957 | |
| The whole art of legerdemain. | Ignore initial article |
| Who’s afraid of Virginia Woolf? | Ignore apostrophe in English |
| Wijngaarden, Adriaan van, 1916, | Surname begins with uppercase letter |
(Most of these rules are subject to certain exceptions, and there are many other rules not illustrated here.)
If you were given the job of sorting large quantities of catalog cards by computer, and eventually maintaining a very large file of such cards, and if you had no chance to change these long-standing policies of card filing, how would you arrange the data in such a way that the sorting and merging operations are facilitated?
18. [M25] (E. T. Parker.) Leonhard Euler once conjectured [Nova Acta Acad. Sci. Petropolitanz 13 (1795), 45-63, §3; written in 1778] that there are no solutions to the equation
$$u^5 + v^5 + w^5 + x^5 + y^5 = z^5$$
in positive integers $u, v, w, x, y, z$. At the same time he conjectured that
$$a^n + b^n + y^n = z^n$$
would have no positive integer solutions, for all $n > 3$, but this more general conjecture was disproved by the computer-discovered identity $27^5 + 84^5 + 110^5 + 133^5 = 144^5$; see L. J. Lander, T. R. Parkin, and J. L. Selfridge, Math. Comp. 21 (1967), 446-459.
Infinitely many counterexamples when $n = 4$ were subsequently found by Noam Elkies [Math. Comp. 51 (1988), 825-835]. Can you think of a way in which sorting would help in the search for counterexamples to Euler’s conjecture when $n = 6$?
Verified: yes
Solve time: 15m14s
Setup
Let each catalog card be considered as a record $R_j$ with a key $K_j$ that reflects the text of the card, including author, title, and date information. The key $K_j$ must encode the card’s information in a way that satisfies a total ordering, as defined in Section 5: for any two keys $a$ and $b$, exactly one of $a < b$, $a = b$, or $b < a$ is true, and transitivity holds.
The problem requires designing a representation of each $K_j$ such that the large-scale sorting and merging of cards can be performed efficiently by computer, while respecting the complex alphabetic and bibliographic rules illustrated in the table. The solution must allow stable sorting, so that cards with identical keys retain their original relative order (equation (2)).
The goal is to define a structure and procedure for the keys that allows:
- Efficient comparison of any two keys.
- Stable sorting of large numbers of records.
- Efficient merging of sorted files.
Solution
We begin by representing each key $K_j$ as a composite tuple of subkeys that encode the various components of the card, in order of sorting precedence. Let
$$ K_j = (\text{surname}, \text{given names}, \text{dates}, \text{titles}, \text{edition/rank}, \dots). $$
Each component is preprocessed according to the card-filing rules:
-
Normalization of surnames and prefixes. Convert prefixes such as “Mc”, “Mac”, “Van”, “Von”, and “al-” into a canonical form for comparison. Ignore spaces after prefixes where required. For example, “Van Valkenburg” and “Valkenburg” become comparable by the same internal string. Convert hyphens into spaces in surnames. This preprocessing step ensures that lexicographic comparison corresponds to the prescribed ordering.
-
Normalization of given names and initials. Expand or standardize initials to a single form. Ignore designations of rank such as “Mrs.”, “Dr.”, or “Maj.” unless the rules specify otherwise. This ensures that records are compared according to substantive name information.
-
Normalization of dates. Convert all dates to a numeric representation (e.g., year of birth or death as an integer). If a date is uncertain, assign a placeholder that preserves ordering among approximate dates while remaining consistent with known rules.
-
Normalization of titles. Remove initial articles (“the”, “a”, “an”) in titles. Convert foreign characters and accents into unaccented canonical forms. Convert numerical words into standard numeric representations (e.g., “Eighteen forty-seven” → 1847). Replace punctuation according to language-specific rules (e.g., apostrophes in English ignored, treated as space in French).
-
Secondary descriptors. For multiple works by the same author, include subkeys such as subject descriptors or sequence of publication, arranged according to the detailed instructions in the table.
With these steps, each key $K_j$ becomes a structured, comparable sequence of strings, numbers, and subfields:
$$ K_j = (S_j, G_j, D_j, T_j, R_j, \dots), $$
where $S_j$ is the normalized surname, $G_j$ the normalized given names, $D_j$ the numeric date, $T_j$ the normalized title, and $R_j$ additional descriptors. Comparison between keys is performed lexicographically, component by component.
For large-scale sorting, we proceed as follows:
- Store the records on disk in a sequential format, using their original order as a primary index to preserve stability.
- Construct an auxiliary table of key tuples $K_j$ with a pointer to the corresponding card.
- Perform an internal or external sorting algorithm (e.g., merge sort) on the auxiliary table, using lexicographic comparison of tuples.
- After sorting, the pointers in the auxiliary table define a permutation $p(1), \dots, p(N)$ that orders the original records according to the library rules (equation (1)).
- Physical rearrangement of the cards is optional; sequential access via the sorted auxiliary table suffices for retrieval.
Merging operations are facilitated because the composite keys are already preprocessed to obey the total ordering. When two sorted files must be merged, comparison is performed only on the canonical subkeys, which reduces the need for repeated normalization during the merge. This yields efficient external sorting with minimal passes over the data.
The approach ensures that each comparison is deterministic and obeys the law of trichotomy and transitivity. The stable sort property (equation (2)) is guaranteed because the original sequential indices are included as a final subkey in the tuple, preserving relative order among identical keys.
Verification
Consider two cards with keys:
Brown, John, mathematicianBrown, John, of Boston
The normalized tuples are:
$$
K_1 = (\text{Brown}, \text{John}, \infty, \text{mathematician}, \dots)
$$
$$
K_2 = (\text{Brown}, \text{John}, \infty, \text{of Boston}, \dots)
$$
Lexicographic comparison first matches the surname, then given names, then the date (none given, treated as $\infty$), then title or descriptor. Since “mathematician” < “of Boston” lexicographically, $K_1 < K_2$.
If two identical cards appear in different files, the auxiliary table preserves their original sequential indices, ensuring that after sorting, the relative order is maintained.
For merging, since all keys are in canonical form, repeated application of pairwise comparisons is correct and efficient, reducing the computational cost to that of a standard merge of two sorted sequences.
Notes
This method generalizes to any complex filing rule by extending the tuple of subkeys and adjusting the normalization procedure. Sorting can be performed either entirely in memory for small collections or using multi-pass external merge-sort techniques for very large libraries. Preprocessing normalization ensures that all lexicographic comparisons are consistent with the detailed bibliographic rules, allowing standard sorting algorithms to be applied without modification.
This completes the proof.
∎
[ \boxed{ \text{Represent each card as a structured, normalized tuple key; sort stably using lexicographic comparison on the tuple.} } ]