这是对第3卷的头一次修订，不仅是对经典计算机排序和查找技术的最全面介绍，而且还对第1卷中的数据结构处理技术作了进一步的扩充，通盘考虑了将大小型数据库和内外存储器。它遴选了一些经过反复检验的计算机方法，并对其效率做了定量分析。第3卷的突出特点是对“最优排序”一节作了修订，对排列论原理与通用散列法作了全新讨论。

关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷已经组成了程序设计理论和实践的惟一的珍贵资源，无数读者都赞扬Knuth的著作对个人的深远影响，科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员已经成功地将他的“菜谱式”的解应用到日常问题上，所有人都由于Knuth在书中表现出的博学、清晰、精确和高度幽默而对他无比敬仰。

第3卷为排序和查找，分“排序”和“查找”两章。本卷全面讨论了计算机排序和查找的一流技术，扩展了第1卷中数据结构的处理方法，将大小数据库以及内存和外部存储都包含在内。

Chapter 5 Sorting

 5.1 Combinatorial Properties of Permutations

5.1.1 Inversions

5.1.2 Permutations of a Multiset

5.1.3 Runs

5.1.4 Tableaux and Involutions

 5.2 Internal sorting

5.2.1 Sorting by Insertion

5.2.2 Sorting by Exchanging

5.2.3 Sorting by Selection

5.2.4 Sorting by Merging

5.2.5 Sorting by Distribution

 5.3 Optimum Sorting

5.3.1 Minimum-Comparison Sorting

5.3.2 Minimum-Comparison Merging

5.3.3 Minimum-Comparison Selection

5.3.4 Networks for Sorting

 5.4 External Sorting

5.4.1 Multiway Merging and Replacement Selection

5.4.2 The Polyphase Merge

5.4.3 The Cascade Merge

5.4.4 Reading Tape Backwards

5.4.5 The Oscillating Sort

5.4.6 Practical Considerations for Tape Merging

5.4.7 External Radix Sorting

5.4.8 Two-Tape Sorting

5.4.9 Disks and Drums

 5.5 Summary, History, and Bibliography

Chapter 6 Searching

 6.1 Sequential Searching

 6.2 Searching by Comparison of Keys

6.2.1 Searching an Ordered Table

6.2.2 Binary Tree Searching

6.2.3 Balanced Trees

6.2.4 Multiway Trees

 6.3 Digital Searching

 6.4 Hashing

 6.5 Retrieval on Secondary Keys

Answers to Exercises

Appendix A: Tables of Numerical Quantities

 1 Fundamental Constants (decimal)

 2 Fundamental Constants (octal)

 3 Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers

Appendix B:Index to Notations

Index and Glossary