The Art of Computer Programming: Volume 3: 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.

1. Tri Dao
2. Dacheng Tao
3. Dan Boneh
4. Christopher R'e
5. Albert Gu
6. Jun Yu
7. Christian Igel
8. Frank Hutter

Citations in the corpus

• Two-Sided Eulerian Numbers via Balls in Boxes (2012, background): “2,3,...} is an example of a permutation statistic. Any function from the set of permutations to a subset of the integers can fairly be called a permutation statistic. The reader is referred to [1] or [13] for more about permutation statistics generally. Anothercommon permutationstatistic isinversion”
• On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract) (2010, unknown): “[37] for background on sorting networks).”
• Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps (2020, background): “Sorting networks (Knuth, 1997) imply that permutation matrices are in ( BB ∗ ) O (log n ) , but we tighten the result to show that they are in fact in BB ∗ (Theorem 2, Appendix G).”
• A Proof Assistant for Higher-Order Logic (2002, background): “Tries are a classic search tree data structure [18] for fast indexing with strings.”
• Simplify: a theorem prover for program checking (2005, methodology): “…but while the main equivalence relation of the E-graph is represented in the root, next, and size .elds using the quick-.nd technique, the congruence relation is represented with the single .eld cgPtr using simple, unweighted Fischer Galler trees [Galler and Fischer 1964; Knuth 1968, Sec.”
• Practical Confidence Intervals for Regression Quantiles (2005, methodology): “For efficient sorting algorithms, we refer to Knuth (1998).”
• Covariance Matrix Adaptation for Multi-objective Optimization (2007, methodology): “We presume an appropriate data structure (say, an AVL-tree, e.g., Knuth, 1973) that allows these look-up, insertion, and deletion operations in O(log N) time, where N is the number of elements in the list.”
• 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].”
• Principles of Communication Systems Simulation with Wireless Applications (2004, methodology): “Specifically, the transfer function of the digital filter, H(z), is defined by [1, 2] H(z) = Ha(s)|s=C(1−z−1)/(1+z−1) (5.”
• The Probability That a Numerical, Analysis Problem Is Difficult (2013, background): “Actually, the question of the distribution of the digits of a floating-point number has a large literature [2], [11], [18], but the discussion in this section does not depend strongly on the actual distribution of digits chosen.”