References for Part Three

---

The primary reference for this section is Volume 3 of Knuth's series, on sorting and searching. Further information on virtually every topic that we have touched upon can be found in this book. In particular, the results discussed here on performance characteristics of the various algorithms are backed up there by complete mathematical analyses.

There is a vast literature on sorting. Knuth and Rivest's 1973 bibliography contains hundreds of references to articles that give insight into the development of many of the classic methods that we have considered. A more up-to-date reference, with an extensive bibliography covering recent work, is the book by Baeza-Yates and Gonnet. A survey of the state of our knowledge about shellsort may be found in Sedgewick's 1996 paper.

For quicksort, the best reference is Hoare's original 1962 paper, which suggests all the important variants, including the use for selection discussed in Chapter 7. Many more details on the mathematical analysis and the practical effects of many of the modifications and embellishments suggested as the algorithm came into widespread use may be found in Sedgewick's 1978 paper. Bentley and McIlroy give a modern treatment of the subject. The material on three-way partitioning in Chapter 7 and three-way radix quicksort in Chapter 10 is based on that paper and the 1997 article by Bentley and Sedgewick. The earliest partitioning-style algorithm (binary quicksort, or radix-exchange sort) appears in the 1959 article by Hildebrandt and Isbitz.

Vuillemin's binomial queue data structure, as implemented and analyzed by Brown, supports all the priority queue operations in an elegant and efficient manner. The pairing heap described by Fredman, Sedgewick, Sleator, and Tarjan is a refinement that is of practical interest.

The 1993 article by McIlroy, Bostic, and McIlroy presents the state of the art in radix sort implementations.

The book by Stone provides some of the background needed to actually put methods like those described in Chapter 11 into practical use. The fundamental ideas described by Stone and the basic methods described in Chapter 11 are only an introduction to this subject, because the onslaught of new devices and new methods of storing and moving information make this subject a volatile one.

R. Baeza-Yates and G. H. Gonnet, Handbook of Algorithms and Data Structures, second edition, Addison-Wesley, Reading, MA, 1984.

J. L. Bentley and M. D. McIlroy, "Engineering a sort function," Software Practice and Experience 23, 1 (January, 1993).

J. L. Bentley and R. Sedgewick, "Sorting and searching strings," Eighth Symposium on Discrete Algorithms, New Orleans, January, 1997.

M. R. Brown, "Implementation and analysis of binomial queue algorithms," SIAM Journal of Computing 7, 3 (August, 1978).

M. L. Fredman, R. Sedgewick, D. D. Sleator, and R. E. Tarjan, "The pairing heap: a new form of self-adjusting heap," Algorithmica 1, 1 (1986).

P. Hildebrandt and H. Isbitz, "Radix exchange an internal sorting method for digital computers," Journal of the ACM, 6, 2 (1959).

C. A. R. Hoare, "Quicksort," Computer Journal, 5, 1 (1962).

D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching, second edition, Addison-Wesley, Reading, MA, 1997.

P. M. McIlroy, K. Bostic, and M. D. McIlroy, "Engineering radix sort," Computing Systems 6, 1 (1993).

R. L. Rivest and D. E. Knuth, "Bibliography 26: Computing Sorting," Computing Reviews, 13 6 (June, 1972).

R. Sedgewick, "Implementing quicksort programs," Communications of the ACM 21, 10 (October 1978).

R. Sedgewick, "Analysis of shellsort and related algorithms," Fourth European Symposium on Algorithms, Barcelona, September, 1996.

H. Stone, High Performance Computer Architecture Addison-Wesley, Reading, MA, 1993.

J. Vuillemin,> "A data structure for manipulating priority queues," Communications of the ACM 21, 4 (April 1978).

---

Top