We consider additive functionals X_n(ϕ) with small toll functions on split trees and a generalization of split trees, which we call fractional split trees, where the split vector does not need to sum up to 1. These additive functionals encompass e.g. the number of nodes, number of leaves and the number of fringe trees of a certain size. We show convergence of the first moment to a limit, which we can explicitly compute if all balls are distributed multinomially and for some models with Beta-distributed splitter. Generally, the first moment is given in terms of negative moments of a perpetuity and can often be approximated to arbitrary precision with known bounds. In split trees and certain fractional split trees, the standard deviation is of smaller order than the first moment, where we show a weak law of large numbers. In other fractional split trees, the standard deviation is of the same order and we show a distribution limit using the contraction method.

QuickXsort is an efficient in situ sequential sorting algorithm that mixes Hoare’s Quicksort algorithm with another sorting algorithm X, such as Heapsort, Insertionsort or Mergesort. The advantage is that QuickXsort can be in-place even if X is not. QuickXsort works recursively like Quicksort but uses sorting algorithm X on one of the sub-lists generated in each step. While the expected complexity of QuickXsort, measured by the number of key comparisons, has been investigated for various choices of X, here the asymptotic variance and distribution of the normalized complexity are studied with Mergesort used as X. Various versions of Mergesort and splitting regimes for the decomposition of the list by Quicksort are considered and periodicities in moments and the distributions are characterized.

The FIND algorithm (also called Quickselect) is a fundamental algorithm to select ranks or quantiles within a set of data. It was shown by Grübel and Rösler that the number of key comparisons required by FIND as a process of the quantiles α ∈ [0,1] in a natural probabilistic model converges after normalization in distribution within the càdlàg space D[0,1] endowed with the Skorokhod metric. We show that the process of the residuals in the latter convergence after normalization converges in distribution to a mixture of Gaussian processes in D[0,1] and identify the limit’s conditional covariance functions. A similar result holds for the related algorithm QuickVal. Our method extends to other cost measures such as the number of swaps (key exchanges) required by FIND or cost measures which are based on key comparisons but take into account that the cost of a comparison between two keys may depend on their values, an example being the number of bit comparisons needed to compare keys given by their bit expansions.