Programming Techniques S. L. Graham, R. L. Rivest Editors Implementing Quicksort Programs Robert Sedgewick Brown University 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. Key Words and Phrases: Quicksort, analysis of algorithms, code optimization, sorting CR Categories: 4.0, 4.6, 5.25, 5.31, 5.5 Introduction One of the most widely studied practical problems in computer science is sorting: the use of a computer to put files in order. A person wishing to use a computer to sort is faced with the problem of determining which of the many available algorithms is best suited for his purpose. This task is becoming less difficult than it once was for three reasons. First, sorting is an area in which the mathematical analysis of algorithms has been particu- larly successful: we can predict the performance of many sorting methods and compare them intelligently. Second, we have a great deal of experience using sorting algo- Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. This work was supported in part by the Fannie and John Hertz Foundation and in part by NSF Grants. No. GJ-28074 and MCS75- 23738. Author's address: Division of Applied Mathematics and Computer Science Program, Brown University, Providence, RI 02912. © 1978 ACM 0001-0782/78/1000-0847 $00.75 847 rithms, and we can learn from that experience to separate good algorithms from bad ones. Third, if the tile fits into the memory of the computer, there is one algorithm, called Quicksort, which has been shown to perform well in a variety of situations. Not only is this algorithm simpler than many other sorting algorithms, but empir- ical [2, ll, 13, 21] and analytic [9] studies show that Quicksort can be expected to be up to twice as fast as its nearest competitors. The method is simple enough to be learned by programmers who have no previous experi- ence with sorting, and those who do know other sorting methods should also find it profitable to learn about Quicksort. Because of its prominence, it is appropriate to study how Quicksort might be improved. This subject has received considerable attention (see, for example, [1, 4, 11, 13, 14, 18, 20]), but few real improvements have been suggested beyond those described by C.A.R. Hoare, the inventor of Quicksort, in his original papers [5, 6]. Hoare also showed how to analyze Quicksort and predict its running time. The analysis has since been extended to the improvements that he suggested, and used to indicate how they may best be implemented [9, 15, 17]. The subject of the careful implementation of Quicksort has not been studied as widely as global improvements to the algorithm, but the savings to be realized are as significant. The history of Quicksort is quite complex, and [15] contains a full survey of the many variants which, have been proposed. The purpose of this paper is to describe in detail how Quicksort can best be implemented to handle actual applications on real computers. A general description of the algorithm is followed by descriptions of the most effective improvements that have been proposed (as demonstrated in [15]). Next, an implementation of Quicksort in a typical high level language is presented, and assembly language implementation issues are con- sidered. This discussion should easily translate to real languages on real machines. Finally, a number of special issues are considered which may be of importance in particular sorting applications. This paper is intended to be a self-contained overview of the properties of Quicksort for use by those who need to actually implement and use the algorithm. A compan- ion paper [17] provides the analytical results which su- port much of the discussion presented here. The Algofithm Quicksort is a recursive method for sorting an array A[1], A[2] ..... A[N] by first "partitioning" it so that the following conditions hold: (i) Some key v is in its final position in the array. (If it is thejth smallest, it is in position A[j].) (ii) All elements to the left of A[j] are less than or equal to it. (These elements A [ 1 ], A [2] ..... A [j - 1 ] are called the "left subtile.") Communications October 1978 of Volume 21 the ACM Number 10(iii) All elements to the right of A[j] are greater than or equal to it. (These elements A [j + 1 ] ..... A IN] are called the "right subtile."] After partitioning, the original problem of sorting the entire array is reduced to the problem of sorting the left and right subfiles independently. The following program is a recursive implementation of this method, with the partitioning process spelled out explicitly. Program 1 procedure quicksort (integer value/, r); comment Sort All : r] where A[r + 1] _> A[/] ..... Air]; if r > I then i:=/;j:= r+ 1; v := A[/]; loop: loop: i := i + 1; while A[i] < v repeat; Ioop:j :=j - 1; while A[]] > v repeat; until j < i: A[i] :=: A[JI; repeat; Alt] :=: A[/3; quicksort(l, j- 1); quicksort(i, r); endif; (This program uses an exchange (or swap) operator :=:, and the control constructs loop ... repeat and if ... endif, which are like those described by D.E. Knuth in [10]. Statements between loop and repeat are iterated: when the while condition fails (or the until condition is satis- fied) the loop is exited immediately. The keyword repeat may be thought of as meaning "execute the code starting at loop again," and, for example, "until j < i"