An asymptotic analysis of the number of comparisons in multipartition quicksort
Kok Hooi Tan · 1993
Quicksort can be generalized by splitting the keys to be sorted into s subsets ($s >$ 2) during each partitioning stage. Quicksort is then the particular case of s = 2. The asymptotic distribution of the number of comparisons in this class of Multipartition Quicksort is studied, with emphasis on the s = 4 version. The exact distribution of T(n), the number of comparisons to sort n keys, is obtained recursively for small n. Exact upper and lower bounds for T(n) are derived, and the asymptotic form of the mean is obtained by a regression approach. A class of recursively constructed distributions on the permutations of keys is derived under which the distribution of T(n) may be found recursively. A theorem of Rosler (1991) that established an asymptotic distribution for ${T(n)-ET(n)}\over {n}$ in Quicksort is generalized to hold under a class of non-uniform distribution of permutations, and to the multipartition setting. The limit distribution is shown to have a positive density function almost everywhere, and to satisfy a fixed-point equation. Numerical methods are used to iteratively approximate the limit distribution. The primary tool is that of successive substitution. The characteristic function, the density, and a random sample from the asymptotic distribution are obtained this way. These methods are computing-intensive, and the efficiency of implementation is considered. In particular, distributed and asynchronous iterative methods are discussed. Two empirical studies compare the performance of Multipartition Quicksort with varying s in terms of the quantity T(n), as well as the actual CPU time for sorting. An analysis of Mergesort is also presented. The asymptotic distribution of the number of comparisons required is shown to be Gaussian.