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 L(Xₙ)= L(XIₙ+X^*n-1-Iₙ+Tₙ) when the "toll function" Tn varies and satisfies general conditions, where (Xn), (Xn*), (In, Tn) are independent, In is uniformly distributed over {0, . . .,n-1}, and L(Xₙ)= L(Xₙ⁾. When the "toll function" Tn (cost needed to partition the original problem into smaller subproblems) is small (roughly n→∞log E(Tₙ)/log n≤ 1/2), Xn is asymptotically normally distributed; nonnormal limit laws emerge when Tn becomes larger. We give many new examples ranging from the number of exchanges in quicksort to sorting on a broadcast communication model, from an in-situ permutation algorithm to tree traversal algorithms, etc.