The art of computer programming, volume 3: (2nd ed.) sorting and searching

By Donald Ervin Knuth. 1998

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

The adaptive radix tree: ARTful indexing for main-memory databases (2013, unknown): “Knuth [17] analyzes these early trie variants.”
Index-driven similarity search in metric spaces (Survey Article) (2003, background): “The vp-tree, one of the more popular instances of ball partitioning, is actually a special case of what Knuth terms a post-of.ce tree whose proposal he attributes to Bruce McNutt in 1972 [Knuth 1998, p. 563].”
The Euler–Maclaurin and Taylor Formulas: Twin, Elementary Derivations (2001, background): “The fourth equation follows from the fact that ∫ n 0 P4 (−t) dt = 0, according to (13) and (12).”
The Melbourne Shuffle: Improving Oblivious Storage in the Cloud (2014, background): “Classic card shuffle methods (e.g., Knuth (or Fisher-Yates) [17], the riffle shuffle [2], Thorp shuffle [24]) are not data-oblivious, however, as anyone observing card swaps or riffles (interleaving two subdecks) of such methods can learn the final output permutation.”
ALEX: An Updatable Adaptive Learned Index (2019, methodology): “Tries [17] use key prefixes instead of B+Tree splitters.”
SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning (2020, methodology): “We also compare a regular full sorting unit (a Batcher’s Odd-Even Sorter [14] to perform merge-sort) to the worst case of the top-k engine (se lecting the median) with an input length of 1024.”
External memory algorithms and data structures: dealing with massive data (2001, methodology): “…can devise a perfect solution, in which the next D blocks needed for the merge are guaranteed to be on distinct disks, based upon the Gilbreath principle [Gardner 1977; Knuth 1998]: we stripe the .rst run into ascending order by disk number, and we stripe the other run into descending order.”