Chaptor 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 34
5.1.4. Tableaux and Involutions 48
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 139
5.2.4. Sorting by Merging 159
5.2.5. Sorting by Distribution 170
5.3.Optimum Sorting 181
5.3.1. Minimum-Comparison Sorting 181
5.3.2. Minimum-Comparison Merging 198
5.3.3. Minimum-Comparison Selection 209
5.3.4. Networks for Sorting 220
5.4.External Sorting 247
5.4.1. Multiway Merging and Replacement Selection 251
5.4.2. The Polyphase Merge 266
5.4.3. The Cascade Merge 289
5.4.4. Reading Tape Backwards 301
5.4.5. The Oscillating Sort 314
5.4.6. Practical Considerations for Tape Merging 320
5.4.7. External Radix Sorting 347
5.4.8. Two-Tape Sorting 352
5.4.9. Disks and Drums 361
5.5.Summary， History， and Bibliography 379
Chapter 6—Searching 389
6.1.Sequential Searching 393
6.2.Searching by Comparison of Keys 406
6.2.1. Searching an Ordered Table 406
6.2.2. Binary Tree Searching 422
6.2.3. Balanced Trees 451
6.2.4. Multiway Trees 471
6.3.Digital Searching 481
6.4.Haahing 508
6.5.Retrieval on Secondary Keys 550
Ansaors to Exorclsos 571
Appondix A—Tablos of Nunoricai Quantitios 701
1. Fundamental Constants （decimal） 701
2. Fundamental Constants （octal） 702
3. Harmonic Numbers， Bernoulli Numbers， Fibonacci Numbers 703
Appondix B—Indox to Notatlona 705
Indox and Glossary 710