Beyond Quicksort

2016 July: Code and more for FourSort, FiveSort and SixSort is available at: github.com/ddccc

2014 February: The algorithms FourSort, FiveSort and SixSort with their parallel versions are described in the paper "Design choices in the Quicksort family with empirical comparisons". It is available at: DesignChoices.pdf

Here the abstract:
Many variants of quicksort have been developed during the last 50 years. We describe design choices that allow classifying a few well known members as well new comers of the quicksort family. The pros and cons of the design choices are illustrated with extensive run-time comparisons of the selected variants. Tests include sorting uniform distributions, weird distributions generated by the Bentley-McIlroy test-bench, distributions of equal values with a varying amount of noise and distributions of sorted data with a variant amount of noise. This collection of test shows at least that there is no overall strict ordering when considering only single threaded algorithms. We do find evidence that single pivot algorithms can be surpassed statistically by two pivot algorithms, which in turn can be surpassed statistically by three pivot algorithms. Our new algorithms FourSort and SixSort outperform qsort with respectively 9% and 24%. Multi-threaded variants outperform single threaded variants. As expected, performance does not scale linearly with the number of threads available to an algorithm. Parallel SixSort with four threads is up to three times faster than single threaded FourSort. Performance variances due to machine cache differences are shown abundantly.

If you need fast in-place sorting contact us: