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-n) = L (XIn + Xn-1-I-n* + T-n) when the toll function T-n varies and satisfies general conditions, where (X-n), (X-n*), (I-n, T-n) are independent, I-n is uniformly distributed over {0,..., n-1}, and L (X-n) = L (X-n*). When the toll function T-n (cost needed to partition the original problem into smaller subproblems) is small (roughly lim sup(n-->infinity) log E (T-n) / log n less than or equal to 1/2), X-n is asymptotically normally distributed; nonnormal limit laws emerge when T-n 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.