arXiv preprint ·
Adaptive Sorting, also in the BST Model
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Cascade: GPU-Accelerated Out-of-Core Suffix Array Construction for LLM Corpora
Online Batching with Lookahead: Adversarial Limits and Stochastic Gains
Solving Restricted Versions of #SAT Faster than $2^m$: Algorithms and Lower Bounds
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
Optimal High Probability Bounds for Random Order Online Sorting
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.