2025/03/28 by Cecilia Holmgren, Jasper Ischebeck, Holmgren, Cecilia +7
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2503.22334
openalex publication_date 2025/03/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a multi-pivot QuickSort algorithm using K∈ℕ pivot elements to partition a nonsorted list into K+1 sublists in order to proceed recursively on these sublists. For the partitioning stage, various strategies are in use. We focus on the strategy that minimizes the expected number of key comparisons in the standard random model, where the list is given as a uniformly permuted list of distinct elements. We derive asymptotic expansions for the expectation and variance of the number of key comparisons as well as a limit law for all K∈ℕ, where the convergence holds for all (exponential) moments. For K≤ 4 we also bound the rate of convergence within the Wasserstein and Kolmogorov--Smirnov distance. Our analysis of the expectation is based on classical results for random m-ary search trees. For the remaining results, combinatorial considerations are used to make the contraction method applicable.