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 requ irement, when property normalized, is asymptotically normally distributed f or m less than or equal to 26 and does not have a fixed limiting distributi on for m > 26. Our tools are based on the method of moments and asymptotic solutions of differential equations, and are applicable to secondary cost m easures of quicksort with median-of-(2t + 1) for which the same phase chang e occurs at t = 58. Both problems are essentially special cases of the gene ralized quicksort of Hennequin in which a sample of tn(t + 1) - 1 elements are used to select m - 1 equi-spaced ranks that are used in turn to partiti on the input into m subfiles. A complete description of the numbers at whic h the phase change occurs is given. For example, when m is fixed and t vari es, the phase change occurs at (in, 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 "asymptot ic transfers" of the underlying recurrence is also given. (C) 2001 John Wil ey & Sons, Inc.