This web page is OCRed from

Donald Knuth's
The Art of Computer Programming
Vol. 3 - SORTING and SEARCHING


last part of Chapter 5 - section 5.5

Pages part of 382 through part of 384
provides a sample of why rowdy computer programmers
speak of Don Knuth in reverent tones.


Knuth's 3 volumes were first copyrighted in 1968,
and are still in print and widely used.
34 years may be a record for any books(s) on computers


(Don Knuth's web page)

[starting near bottom of page 382] SUMMARY, HISTORY, AND BIBLIOGRAPHY


Early developments.
A search for the origin of today's sorting techniques takes us back to the nineteenth century, when the first machines for sorting were invented. The United States conducts a census of all its citizens, every ten years, and by 1880 the problem of processing the voluminous census data was becoming very acute; in fact, the total number of single (as opposed to married) people was never tabulated that year, although the necessary information had been gathered. Herman Hollerith, a 20-year-old employee of the Census Bureau, devised an ingenious electric tabulating machine to meet the need for better statistics-gathering, and about 100 of his machines were successfully used to tabulate the 1890 census rolls.

Figure 94 similar image provided here shows Hollerith's original battery-driven apparatus; of chief interest to us is the "sorting box" at the right, which has been opened to show half of the 26 inner compartments. The operator would insert a 6 5/8" X 3 1/4" punched card into the "press" and lower the handle; this caused spring-actuated pins in the upper plate to make contact with pools of mercury in the lower plate, wherever a hole was punched in the card. The corresponding completed circuits would cause associated dials on the panel to advance by one unit; and furthermore, one of the 26 lids of the sorting box would pop open. At this point the operator would reopen the press, put the card into the open compartment, and close the lid. One man reportedly ran 19071 cards through this machine in a single 6 1/2-hour working day, an average of about 49 cards per minute! (A typical operator would work at about one-third this speed.)

Population continued its inexorable growth pattern, and the original tabulator-sorters were not fast enough to handle the 1900 census; so Hollerith devised another machine to stave off another data processing crisis. His new device (patented in 1901 and 1904) had an automatic card feed, and in fact it looked essentially like modern card sorters. The story of Hollerith's early machines has been told in interesting detail by Leon E. Truesdell, The Development of Punch Card Tabulation (Washington: U.S. Bureau of the Census, 1965); see also the contemporary accounts in Columbia College School of Mines Quarterly 10 (1889), 238-255; d. Franklin Inst. 129 (1890), 300-306; The Electrical Engineering 12 (Nov. 11, 1891), 521-530; J. Amer. Statistical Assn. 2 (1891), 330-341, 4 (1895), 365; J. Royal Statistical Soc. 55 (1892), 326-327; Allgemeines Statistisches Archiv 2 (1892), 78-126; J. Soc. Statistique de Paris 33 (1892), 87-96; U.S. Patents 595781 (1889), 685608 (1901), 777,209 (1904). Hollerith and another former Census Bureau employee, James Powers, went on to found rival companies which eventually became part of IBM and Remington Rand corporations, respectively.

Hollerith's sorting machine is, of course, the basis for radix sorting methods now used in digital computers. His patent mentions that two-column numerical items are to be sorted "separately for each column," but he didn't say whether or not the units or the tens columns should be considered first. The nonobvious trick of using the units column first was presumably discovered by some anonymous mous machine operator and passed on to others (cf. Section 5.2.5); it appears' in the earliest extant IBM sorter manual (1936). The first known mention of this right-to-left technique is an incidental remark which appears in an article by L. J. Comrie, Trans. of the Ofce Machinery Users' Assoc. (London, 1930), 25-37.