data structure developers

Abstract: Sorting is one of the most basic algorithmic problems. Adaptive sorting algorithms exploit features that make an input easier to sort, often captured by entropy measures. Many such measures have been studied, raising two natural questions: how do they relate to one another, and are there algorithms that are adaptive to them? We complete a hierarchy of relations between previously studied entropy measures and show that the classical measure Reg is a source of this hierarchy. We prove that an existing data structure yields a Reg-adaptive sorting algorithm, thereby achieving the adaptive bounds of every measure in the hierarchy. Following McIlroy's observation that Reg has a mathematically inconvenient definition, we study a slightly weaker but simpler measure, reg. For inputs without duplicates, we show that O(n + log reg) = O(n + log Reg), so this simplification preserves the adaptive bound. Finally, we do algorithms design and introduce SproutSort, a reg-adaptive algorithm in the offline binary search tree (BST) model. SproutSort achieves an access cost of O(n + log reg), making it the most adaptive algorithm in this model to date. We also introduce SkeletonSort, a simple randomised pointer-machine algorithm that sorts distinct keys in expected O(n + log reg) time, offering a considerably simpler implementation of a sorting algorithm this high in the adaptive hierarchy.

Abstract: We revisit the implicit membership problem in Yao's full-table model [Yao, 1981] and obtain, to our knowledge, the first quantitative improvements to his 45-year-old Ramsey bounds, most notably reducing the two-probe bound from tower-type to polynomial. In this model, an $n$-set $S\subseteq\{1,\ldots,m\}$ is stored as a permutation in an $n$-cell table, and queries decide whether $x\in S$. Let $G_q(n)$ be the largest universe size admitting a $q$-probe membership scheme for all $n$-sets. Yao determined the one-probe case exactly, proving $G_1(n)=2n-2$ for $n>2$, but the behavior for $q\ge2$ remained wide open. Fiat and Naor [1993] constructed schemes for universes of size $\exp(n^c)$ for some constant $c>0$ and sufficiently large constant $q$. For the first adaptive case, $q=2$, we prove $G_2(n)=O(n^2(\log n)^2)$. For every fixed integer $q\ge3$, we show that $G_q(n)$ is at most a tower of height $q-1$ with top $n^{1+o(1)}$; in particular, $G_3(n)\le\exp(n^{1+o(1)})$. The two-probe proof avoids Ramsey theory altogether; for larger fixed $q$, we use Ramsey theory only to make the first $q-1$ probes follow a fixed pattern, and then handle the last probe by the same non-Ramsey argument. Somewhat surprisingly, for each fixed $q$, we also show that implicit membership is as hard as implicit search up to a polynomial loss in universe size. Implicit search must return the cell containing $x$ when present and reject otherwise. For the analogous search threshold $H_q(n)$, we prove $H_q(n)\le G_q(n)\le n^q(H_q(n)+1)^{q+1}$ for every $q,n$. Thus, for every fixed $q$, one threshold is at most $\exp(n^{O(1)})$ if and only if the other is. The proofs were first generated by ChatGPT 5.5 Pro without mathematical hints; the membership-search equivalence emerged while pursuing an improved four-probe bound. The authors have validated and edited the proofs and assume responsibility for all content.