A Detailed Analysis of Quicksort Algorithms with Experimental Mathematics

By Yukun Yao

.pdf   LaTeX source  

Written: April-May 2019

We study several variants of single-pivot and multi-pivot Quicksort algorithms and consider them as discrete probability problems. With experimental mathematics, explicit expressions for expectations, vari- ances and even higher moments of their numbers of comparisons and swaps can be obtained. For some variants, Monte Carlo experiments are performed, the numerical results are demonstrated and the scaled limiting distribution is also discussed.

Accompanying Maple package is QuickSort.txt and Findrec.txt