Phase changes in random m ‐ary search trees and generalized quicksort

We propose a uniform approach to describe the phase change of the limiting distribution of space measures in random m ‐ary search trees: the space requirement, when properly normalized, is asymptotically normally distributed for m ≤26 and does not have a fixed limiting distribution for m >26. Our tools are based on the method of moments and asymptotic solutions of differential equations, and are applicable to secondary cost measures of quicksort with median‐of‐(2 t +1) for which the same phase change occurs at t =58. Both problems are essentially special cases of the generalized quicksort of Hennequin in which a sample of m ( t +1)−1 elements are used to select m −1 equi‐spaced ranks that are used in turn to partition the input into m subfiles. A complete description of the numbers at which the phase change occurs is given. For example, when m is fixed and t varies, the phase change occurs at ( m ,  t )={(2, 58), (3, 19), (4, 10), (5, 6), (6, 4), …}. We also indicate some applications of our approach to other problems including bucket recursive trees. A general framework on “asymptotic transfers” of the underlying recurrence is also given. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 316–358, 2001