Quicksort is one of the best-known algorithms in computer science. The algorithm selects one value from the array, which it calls the pivot. The array is then divided into two segments: values that are less than or equal to the pivot, and values that are greater than or equal to the pivot. If we partition using two pivots at once, the array is divided into three segments. In general, any quicksort that uses more than one pivot is known as a multi-pivot quicksort.
It is well known from theoretical analysis that multi-way quicksorts do not reduce the total amount of work that the sort must perform. Although splitting the array into three segments reduces the total number of splitting passes that are needed, each splitting pass is more expensive. However, in 2009 the sort in the Java 7 standard library started to use a two-pivot quicksort because it is a little faster in practice. The main reason is that two-pivot quicksort exhibits better data locality than the two-pivot version because it requires fewer passes over large data segments.
The goal of this project is to design, implement and evaluate multi-pivot quicksort algorithms. You should expect to implement algorithms with at least 2, 3, 4, 5, 6 and 7 pivots. Writing code for larger numbers of pivots can be quite repetitive, and it might therefore make sense to write a small code generator to create the code. I have some ideas about how to improve these algorithms.
This is a challenging project that is unsuitable for the great majority of students. The project might suit someone who has competed successfully in international programming competitions where there are many algorithmic problems to solve. Multi-pivot quicksort algorithms are complicated, and the programming is not simple. Furthermore, the execution time benefits of using multiple pivots are often small. The goal of the project is to study a small corner of sorting algorithms that has not yet been fully studied, not to find the best way to make sorting algorithms faster. It is difficult to imagine programming this project in any language other than C++.