Additional Material

“How Good is Multi-Pivot Quicksort?”

Contact: Martin Aumüller,



Needs g++, cmake in version >= 2.8, and libboost-random. For performance measurements it uses libpapi. To generate quicksort variants automatically, ruby is needed.

How to build

Use the following commands on the top-level directory of the project.

mkdir bin; cd bin

cmake …


For a release build with optimization flags, use

cmake -DCMAKE_BUILD_TYPE=Release ..

After successful compilation, the executable is located at build/src/qstest.

Note that most quicksort algorithms must be generated first, see below.

Example Calls

Example calls to build the source code and generate quicksort variants automatically can be found in the directory ``examples’’. Example invocation:

cd examples; make

Generates the binary.

./qs-example -a list

Lists the available algorithms.

./qs-example -a q -s 16m -S 64m -r 100 permutation

Tests all available algorithms on the same 100 random permutations for inputs containing 2^14, 2^15, or 2^16 64-bit integers.


Basic toolkit to run experiments and measure running times provided by Timo Bingmann. The same author also provided basic source code which was used for the implementation of the “Permute_k” and “Copy_k” algorithms. (

Written September 24, 2015 by Martin Aumüller.