arXiv preprint ·
The Movement Complexity of Sorting
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The complexity of sorting is usually measured by the number of comparisons. This measure ignores the movement of the read heads between comparisons, which is a real cost on many machines. We study this cost on its own. Keys lie on a $d$-dimensional grid, two heads move over the grid and compare the keys beneath them, and the only cost is the total movement of the heads. The algorithm plans its route in $r$ rounds and sees the outcomes of each round only after running it. For every $d$ and $r$ we determine the expected movement needed to sort $n$ keys: it is $n^β$ up to polylogarithmic factors, where $β=1+D^{r-1}/(D^{r}-(D-1)^{r})$ and $D=2d$, falling from $n^{2}$ at $r=1$ to $n^{1+1/(2d)}$ with unlimited rounds. Our algorithm makes every round move about the same amount, and a matching lower bound holds against every algorithm.
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
Limits and Constants of OpenAI's Claimed ETH Refutation
An $\mathsf{FPRAS}$ for Mixed Volumes
Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know
Quantum Lower Bounds for Collision Problems
Leaving Quantum Bias on the Table: Pushforwards as a Path to Quantum Advantage in Constrained Optimization
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.