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

《计算机程序设计艺术》系列被公认为计算机科学领域的权威之作，深入阐述了程序设计理论，对计算机领域的发展有着极为深远的影响。本书是该系列的第3卷，扩展了第1卷中信息结构的内容，主要讲排序和查找。书中对排序和查找算法进行了详细的介绍，并对各种算法的效率做了大量的分析。

本书适合从事计算机科学、计算数学等各方面工作的人员阅读，也适合高等院校相关专业的师生作为教学参考书，对于想深入理解计算机算法的读者，是一份必不可少的珍品。

《计算机程序设计艺术》系列著作对计算机领域产生了深远的影响。这一系列堪称一项浩大的工程，自1962年开始编写，计划出版7卷，目前已经出版了4卷。《美国科学家》杂志曾将这套书与爱因斯坦的《相对论》等书并列称为20世纪最重要的12本物理学著作。

本书是该系列的第3卷，扩展了第1卷中信息结构的内容，主要讲排序和查找。书中对排序和查找算法进行了详细的介绍，并对各种算法的效率做了大量的分析。