《the art of computer programming P726》

Chaptor 5—Sorting1

5.1.Combinatorial Properties of Permutations11

5.1.1. Inversions11

5.1.2. Permutations of a Multiset22

5.1.3. Runs34

5.1.4. Tableaux and Involutions48

5.2.Internal Sorting73

5.2.1. Sorting by Insertion80

5.2.2. Sorting by Exchanging105

5.2.3. Sorting by Selection139

5.2.4. Sorting by Merging159

5.2.5. Sorting by Distribution170

5.3.Optimum Sorting181

5.3.1. Minimum-Comparison Sorting181

5.3.2. Minimum-Comparison Merging198

5.3.3. Minimum-Comparison Selection209

5.3.4. Networks for Sorting220

5.4.External Sorting247

5.4.1. Multiway Merging and Replacement Selection251

5.4.2. The Polyphase Merge266

5.4.3. The Cascade Merge289

5.4.4. Reading Tape Backwards301

5.4.5. The Oscillating Sort314

5.4.6. Practical Considerations for Tape Merging320

5.4.7. External Radix Sorting347

5.4.8. Two-Tape Sorting352

5.4.9. Disks and Drums361

5.5.Summary， History， and Bibliography379

Chapter 6—Searching389

6.1.Sequential Searching393

6.2.Searching by Comparison of Keys406

6.2.1. Searching an Ordered Table406

6.2.2. Binary Tree Searching422

6.2.3. Balanced Trees451

6.2.4. Multiway Trees471

6.3.Digital Searching481

6.4.Haahing508

6.5.Retrieval on Secondary Keys550

Ansaors to Exorclsos571

Appondix A—Tablos of Nunoricai Quantitios701

1. Fundamental Constants （decimal）701

2. Fundamental Constants （octal）702

3. Harmonic Numbers， Bernoulli Numbers， Fibonacci Numbers703

Appondix B—Indox to Notatlona705

Indox and Glossary710