Quicksort at Fifty: Implementing and Analyzing a Family of Functions
Speaker: Jon Bentley, Avaya Labs Research
Date: Monday, December 3 2012
Time: 2:45PM to 3:45PM
Location: 32-D463 (Stata Center - Star Conference Rm)
Host: Charles E. Leiserson, MIT CSAIL
Contact: Marcia Davidson, 617-253-2322, email@example.comRelevant URL:
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.