CSAIL Event Calendar

Quicksort at Fifty: Implementing and Analyzing a Family of Functions

For half a century, the fastest comparison-based sort functions have been variants of Hoare’s 1962 classic Quicksort. But exactly which variants are best on today’s machines? This talk describes experiments to search for the fastest possible implementation of Quicksort; our hunt is a celebration of the Joy of Programming. We were surprised by the results: some old champions are now painfully slow, while long-discarded variants have become lightning fast. Along the way, we discovered a desperate need for a new cost model for sorting, and we laid the foundation for the Dual-Pivot Quicksort we wrote for Java Development Kit 7. We found that explicitly considering a large family (or product line) of algorithms is a powerful approach.

(This talk describes joint work with Vladimir Yaroslavskiy and Joshua Bloch.)

Jon Bentley is a computer scientist at Avaya Labs Research. His research interests include programming techniques, algorithm design, and the design of software tools and interfaces. He is the author of three books: Writing Efficient Programs, Programming Pearls (two editions), and More Programming Pearls. He has written articles on a variety of topics, ranging from the theory of algorithms to software engineering. He received a B.S. from Stanford in 1974 and an M.S. and Ph.D. from the University of North Carolina in 1976, then taught Computer Science at Carnegie Mellon for six years. He joined Bell Labs Research in 1982, and retired in 2001 to join Avaya. He has been a visiting faculty member at West Point and Princeton, and has been a member of teams that have shipped software tools, telephone switches, telephones and web services.

See other events happening in December 2012