In 1959 IBM shipped the 084, a card sorter that moved 2,000 cards a minute and read one column of each. A card had 80 columns and 12 rows. The machine held each card against the feed by suction, passed it under a photocell, found the hole in whichever column the operator had selected, and dropped the card into one of thirteen pockets, one for each row and one for cards it could not read. It did nothing else. Every IBM sorter before it had done the same thing more slowly, with a wire brush instead of a photocell.

A single column is not much of a key. To put a deck in order by a five-digit part number, the operator set the reader to the fifth column, ran the deck, stacked the pockets in order from 0 to 9, set the reader to the fourth column, and ran the deck again. Five passes for five digits. The least significant digit went first because each later pass kept the order the earlier passes had made: cards with the same fourth digit landed in the same pocket in the order they arrived, which was already sorted on the fifth. Letters cost more. The alphabet was coded with two holes in a column, one in the digit rows and one in the three zone rows at the top, so an alphabetic column took two passes, and a five-letter name took ten. Textbooks later gave the method a name, radix sort. In a machine room it was called sorting.

The operation is older than the automation. The sorter that Herman Hollerith supplied for the 1890 census was an oak box with 26 compartments in two rows, each under a brass lid held shut by an electric catch. A cable ran to the tabulator. A clerk laid a card in the tabulator’s press, pins went through the holes into cups of mercury, the dials advanced, and somewhere on the box a lid popped open. The clerk put the card in that compartment and closed the lid. The machine chose the compartment and a person carried the card there, about 7,000 times a day. The count of the population, 62,622,250, was finished on 12 December 1890. In 1901 Hollerith’s company built a sorter that moved the card itself.

On 23 January 1959, Edward Fredkin at Bolt Beranek and Newman in Cambridge, Massachusetts, circulated an internal memo titled “Trie Memory.” The Communications of the ACM published it in September 1960. The same year, René de la Briandais presented “File searching using variable length keys” at the Western Joint Computer Conference, describing the same structure. Fredkin took the name from the middle of “retrieval.” The structure works like this. The first character of a key selects one cell in a register of cells. That cell points to another register, in which the second character selects a cell, and so on down until the key runs out. Every register is a pocket, and every level is a pass through the sorter. The difference is that nobody stacks the pockets and runs the deck again. Each pocket stays where it fell, with a pointer to the pockets below it. To find a key you walk down. To find every key that begins with a given prefix you walk down as far as the prefix goes and then read everything underneath. Fredkin’s reference list includes Claude Shannon’s 1951 paper on how well a reader of English can guess the next letter of a text. The memo was about storage, but the author had partial keys on his mind.

The partial key reached the keyboard at the same company ten years later. Tenex, the operating system BBN wrote for the PDP-10 in 1969, had long command names, on the order of DIRECTORY (OF FILES). A user could type DIR and press escape, and the system would fill in the rest. A question mark instead of escape printed a list of everything that could legally follow and then put the user back where they had been. The feature worked on file names as well as commands. Escape gave you the one card in the pocket if there was only one. The question mark showed you the pocket. Ken Greer at Carnegie Mellon began copying the behaviour into the Unix C shell in September 1975 and finished merging it in December 1981, and the t in tcsh stands for Tenex.

Completion finishes a word the system already knows. Prediction guesses one. John Darragh’s 1988 master’s thesis at the University of Calgary, supervised by Ian Witten, described a program called the Reactive Keyboard, published in the November 1990 issue of Computer. It built a statistical model of whatever text the user had typed so far and displayed a menu of likely continuations. The Macintosh version needed one megabyte of memory and no physical keyboard, since the user entered text by pointing at the menu. It was built for people with physical disabilities for whom typing was slow or impossible. Its reference list also includes Shannon’s 1951 paper. The trie held a fixed dictionary, filled once; here the pockets refilled as the user typed, and the order inside each pocket came from how often the user had chosen that way before.

T9 came out of the same kind of work. Tegic Communications was founded in Seattle in the mid-1990s by Martin King, Cliff Kushler and Dale Grover, who had all built devices for people who could not use a keyboard. King had made a communicator driven by eye movement, and Kushler had spent nearly a decade at Prentke Romich, a maker of augmentative communication aids. Their question had been how to enter text from eight eye positions, and the answer turned out to fit a telephone keypad. A phone has nine lettered keys with three or four letters each, so 4-3-5-5-6 is “hello” and also every other word that uses those keys in that order. The pocket at each level now belongs to several letters at once, and a dictionary ranked by word frequency decides which word the user meant. That is a real change to the operation. The sorter never had to guess which hole it had found.

Google Suggest was Kevin Gibbs’s 20-percent project in 2004, begun as a way to complete URLs and moved to search queries when that proved more useful. It launched in Google Labs in December 2004, after Yahoo and Ask had already offered similar drop-downs, and became the default on google.com in 2008. The pocket now held the queries other people had typed, ranked by how often they had typed them. Before it could launch, someone had to decide which queries the box should never show, and there was no algorithm for that. Gibbs made the list himself.

Every autocomplete box in use is a sorter that has been stopped partway through a run, showing the contents of one pocket. The pocket is the same pocket Hollerith’s clerk closed a lid on in 1890, and the walk down to it is the walk Fredkin described in 1959. What has changed is only what is inside and in what order. Hollerith’s compartments held whatever fell into them, in the order it fell. The suggestion box holds what the operator has agreed to leave there, in the order everyone else preferred it. The machine is a century old. The editorial decision is the part that is new.