Implementing Quicksort programs
Robert Sedgewick · Communications of the ACM · 1978
This paper is a practical study of how to implement the Quicksort sorting algorithm and its best variants on real computers, including how to apply various code optimization techniques. A detailed implementation combining the most effective improvements to Quicksort is given, along with a discussion of how to implement it in assembly language. Analytic results describing the performance of the programs are summarized. A variety of special situations are considered from a practical standpoint to illustrate Quicksort's wide applicability as an internal sorting method which requires negligible extra storage.
Cited by 288 works. doi:10.1145/359619.359631
Authors
References
- The Art of Computer Programming
- Algorithms+Data Structures = Programs
- The art of computer programming. Vol.1: Fundamental algorithms
- Structured Programming with go to Statements
- Algorithm 64: Quicksort
- Programming languages and their compilers: Preliminary notes
- Quicksort
- Algorithm 347: an efficient algorithm for sorting with minimal storage [M1]
- Samplesort: A Sampling Approach to Minimal Storage Tree Sorting
- The analysis of Quicksort programs