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.

In this extended abstract a general framework is developed to bound rates of convergence for sequences of random variables as they mainly arise in the analysis of random trees and divide-and-conquer algorithms. The rates of convergence are bounded in the Zolotarev distances. Concrete examples from the analysis of algorithms and data structures are discussed as well as a few examples from other areas. They lead to convergence rates of polynomial and logarithmic order. Our results show how to obtain a significantly better bound for the rate of convergence when the limiting distribution is Gaussian.

In 2009, Oracle replaced the long-serving sorting algorithm in its Java 7 runtime library by a new dual-pivot Quicksort variant due to Vladimir Yaroslavskiy. The decision was based on the strikingly good performance of Yaroslavskiy's implementation in running time experiments. At that time, no precise investigations of the algorithm were available to explain its superior performance—on the contrary: previous theoretical studies of other dual-pivot Quicksort variants even discouraged the use of two pivots. In 2012, two of the authors gave an average case analysis of a simplified version of Yaroslavskiy's algorithm, proving that savings in the number of comparisons are possible. However, Yaroslavskiy's algorithm needs more swaps, which renders the analysis inconclusive. To force the issue, we herein extend our analysis to the fully detailed style of Knuth: we determine the exact number of executed Java Bytecode instructions. Surprisingly, Yaroslavskiy's algorithm needs sightly more Bytecode instructions than a simple implementation of classic Quicksort—contradicting observed running times. As in Oracle's library implementation, we incorporate the use of Insertionsort on small subproblems and show that it indeed speeds up Yaroslavskiy's Quicksort in terms of Bytecodes; but even with optimal Insertionsort thresholds, the new Quicksort variant needs slightly more Bytecode instructions on average. Finally, we show that the (suitably normalized) costs of Yaroslavskiy's algorithm converge to a random variable whose distribution is characterized by a fixed-point equation. From that, we compute variances of costs and show that for large n , costs are concentrated around their mean.

Tries are among the most versatile and widely used data structures on words. They are pertinent to the (internal) structure of (stored) words and several splitting procedures used in diverse contexts ranging from document taxonomy to IP addresses lookup, from data compression (i.e., Lempel-Ziv'77 scheme) to dynamic hashing, from partial-match queries to speech recognition, from leader election algorithms to distributed hashing tables and graph compression. While the performance of tries under a realistic probabilistic model is of significant importance, its analysis, even for simplest memoryless sources, has proved difficult. Rigorous findings about inherently complex parameters were rarely analyzed (with a few notable exceptions) under more realistic models of string generations. In this paper we meet these challenges: By a novel use of the contraction method combined with analytic techniques we prove a central limit theorem for the external path length of a trie under a general Markov source. In particular, our results apply to the Lempel-Ziv'77 code. We envision that the methods described here will have further applications to other trie parameters and data structures.

We consider the problem of recovering items matching a partially specified pattern in multidimensional trees (quad trees and k-d trees). We assume the traditional model where the data consist of independent and uniform points in the unit square. For this model, in a structure on n points, it is known that the number of nodes Cn (ξ) to visit in order to report the items matching an independent and uniformly on [0,1] random query ξ satisfies E[Cn(ξ)] ∼ κnβ, where κ and β are explicit constants. We develop an approach based on the analysis of the cost Cn (x) of any fixed query x ∊ [0, 1], and give precise estimates for the variance and limit distribution of the cost Cn (x). Our results permit to describe a limit process for the costs Cn(x) as x varies in [0, 1]; one of the consequences is that E[maxx∊[0, 1] Cn(x)] ∼ γnβ; this settles a question of Devroye [Pers. Comm., 2000].

For the random binary search tree with n nodes inserted the number of ancestors of the elements with ranks k and $\ell$, $1 \le k < \ell \le n$, as well as the path distance between these elements in the tree are considered. For both quantities, central limit theorems for appropriately rescaled versions are derived. For the path distance, the condition $\ell-k \to \infty$ as $n\to \infty$ is required. We obtain tail bounds and the order of higher moments for the path distance. The path distance measures the complexity of finger search in the tree.

We characterize all limit laws of the quicksort-type random variables defined recursively by ${\cal L}(X_n)= {\cal L}(X_{I_n}+X^*_{n-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 ${\cal L}(X_n)={\cal L}(X_n^\ast)$. When the "toll function" T n (cost needed to partition the original problem into smaller subproblems) is small (roughly $\limsup_{n\rightarrow\infty}\log E(T_n)/\log n\le 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.