Chapter 5 Sorting 1 *5.1. Combinatorial Properties of Permutations 11 *5.1.1. Inversions　　　11 *5.1.2. Permutations of a Multiset　　22 *5.1.3. Runs　　35 *5.1.4. Tableaux and Involutions　 47 5.2. Internal sorting　　　　73 5.2.1. Sorting by Insertion　　　80 5.2.2. Sorting by Exchanging　　　　105 5.2.3. Sorting by Selection　　138 5.2.4. Sorting by Merging　　　158 5.2.5. Sorting by Distribution　168 5.3. Optimum Sorting 180 5.3.1. Minimum-Comparison Sorting　 180 *5.3.2. Minimum-Comparison Merging　 197 *5.3.3. Minimum-Comparison Selection　207 *5.3.4. Networks for Sorting　　219 5.4. External Sorting　　　248 5.4.1. Multiway Merging and Replacement Selection　 252 *5.4.2. The Polyphase Merge　　　　267 *5.4.3. The Cascade Merge　288 *5.4.4. Reading Tape Backwards　 299 *5.4.5. The Oscillating Sort 　 311 *5.4.6. Practical Considerations for Tape Merging　317 *5.4.7. External Radix Sorting　　　　343 *5.4.8. Two-Tape Sorting　　348 *5.4.9. Disks and Drums356 5.5. Summary, History, and Bibliography　 380 Chapter 6 Searching　　392 6.1. Sequential Searching 　 396 6.2. Searching by Comparison of Keys　 409 6.2.1. Searching an Ordered Table　 409 6.2.2. Binary Tree Searching　 426 6.2.3. Balanced Trees　　 458 6.2.4. Multiway Trees 　　481 6.3. Digital Searching 492 6.4. Hashing　　513 6.5. Retrieval on Secondary Keys　　　　559 Answers to Exercises 　584 Appendix A Tables of Numerical Quantities 748 1. Fundamental Constants (decimal)　 748 2. Fundamental Constants (octal)　 749 3. Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers 750 Appendix B Index to Notations　 752 Index and Glossary 757