Phase Change of Limit Laws in the Quicksort Recurrence Under Varying Toll Functions

We characterize all limit laws of the quicksort type random variables defined recursively by Xn = X In + X n 1 In + Tn when the "toll function" Tn varies and satisfies general conditions, where (Xn ), (X n ), (I n ; Tn ) are independent, Xn n , and I n is uniformly distributed over f0; : : : ; n 1g. When the "toll function" Tn (cost needed to partition the original problem into smaller subproblems) is small (roughly lim sup n!1 log E(Tn )= log n 1=2), Xn is asymptotically normally distributed; non-normal limit laws emerge when Tn becomes larger. We give many new examples ranging from the number of exchanges in quicksort to sorting on broadcast communication model, from an in-situ permutation algorithm to tree traversal algorithms, etc