Multi-Pivot Quicksort: Theory and Experiments

Recently Vladimir Yaroslavskiy proposed a dual pivot quicksort algorithm that, contrary to prior theory and intuition, outperforms standard quicksort by a a significant margin under the Java JVM. More recently, this algorithm has been analysed in terms of comparisons and swaps by Wild and Nebel. In this talk we first review the results of similar experiments using a native C implementation thus removing potential extraneous effects of the JVM. Second, we provide analyses on L1/RAM cache behavior of various quicksort algorithms. We then provide strong evidence that cache behavior is causing most of the performance differences in these algorithms.

Lastly, we build upon prior work in multi-pivot quicksort and propose a 3-pivot variant showing a 7-8% performance improvement over the previously best known quicksort algorithms.


Dr. Alex Lopez-Ortiz is a Professor and Cheriton Faculty Fellow in the School of Computer Science at the University of Waterloo. Alex has authored over 120 refereed publications applying theoretical insights to a variety of topics such as search engine algorithms, data streams, video on demand, data compression and paging. He has also held management positions in research and development in industry, where he led the research and development of performance critical software projects.