The Art of Computer Programming, Volume 3: Sorting and Searching (2nd Edition) 3

This volume comprises Chapters 5 and 6 of the complete series. Chapter 5 is concerned with sorting into order; this is a large subject that has been divided chiefly into two parts, internal sorting and external sorting. There also are supplementary sections, which develop auxiliary theories about permutations (Section 5.1) and about optimum techniques for sorting (Section 5.3). Chapter 6 deals with the problem of searching for specified items in tables or files; this is subdivided into methods that search sequentially, or by comparison of keys, or by digital properties, or by hashing, and then the more difficult problem of secondary key retrieval is considered. There searching related to sorting is a surprising amount of interplay between both chapters, with strong analogies tying the topics together. Two important varieties of information structures are also discussed, in addition to those considered in Chapter 2, namely priority queues (Section 5.2.3) and linear lists represented as balanced trees (Section 6.2.3). 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 Appendix C — Index to Algorithms and Theorems Index and Glossary