Multi-Pivot Quicksort: an Experiment with Single, Dual, Triple, Quad, and Penta-Pivot Quicksort Algorithms in Python

Abstract

Dual-pivot quicksort, which was proposed by Yaroslavsky, has been experimentally proven to be more efficient than the classical single-pivot quicksort under the Java Virtual Machine [6]. Moreover, Kushagara, López-Ortiz, and Munro [4] has shown that triple-pivot quicksort runs 7-8% faster than dual-pivot quicksort in C, mutatis mutandis. In this research, we implement and experiment with single, dual, triple, quad, and penta-pivot quicksort algorithms in Python. Our experimental results are as follows. Firstly, the quicksort with single pivot is the slowest among the five variants. Secondly, at least until five (penta) pivots are being used, it is proven that the more pivots are used in a quicksort algorithm, the faster its performance becomes. Thirdly, the increase of speed resulted by adding more pivots tends to decrease gradually.