Shellsort gaps learned by AI improve sorting efficiency beyond old limits
A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$
Computational ComplexityData Structures and AlgorithmsMachine Learning
Summary
Sorting data quickly depends partly on choosing good steps, called gaps, but picking these has been hard for decades. The authors used artificial intelligence to search through many possible gap sequences without relying on past hand-designed rules. Their system found a gap sequence that sorts faster on very large lists than anyone’s method in a long time. This discovery also comes with theoretical proof that it beats an important previous speed limit for practical sparse sequences.
What this means in practice
- •For software engineers: Implement improved Shellsort gap sequences for faster sorting of very large datasets.
- •For database developers: Optimize indexing or batch sorting tasks using newly discovered gap sequences to reduce comparison and move operations.
Authors
Bo Liu
Abstract
Choosing Shellsort gaps is a well-known open problem. For over sixty years, successful sequences have relied on human-designed formulas, numerical searches, or number-theoretic constructions. Although stronger general bounds exist for dense or mainly theoretical families, the worst-case upper bound for a short, sparse, and practically competitive construction has not advanced beyond $N^{4/3}$ for decades. We ask whether the sequence itself can instead be learned from execution. We present an RL-driven, self-supervised system that searches over executable gap generators. Every proposal is valid by construction, and executed candidates return exact comparison and move counts; no classical sequence is used as a target. Across five independent searches, the system discovers a common rational-geometric family. A second self-supervised stage tunes only a finite prefix, producing the practical sequence $1,3,8,20,47,116,300,585,1416,3303,\ldots$. Once frozen, it obtains the lowest equal-task average operation count among seven classical baselines on 25 large tasks with $10^7<N\leq 10^8$. We complete the learned tail without changing its practical behavior: only beyond $10^{1000}$, a zero-density set of unit companions $h_s+1$ removes the remaining congruence barriers. The resulting sparse sequence has matching polynomial upper and lower exponents, up to polylogarithmic factors: $Ω(N^{1.024296451657\ldots}) \leq T(N) \leq O(N^{1.024296451657\ldots}\operatorname{polylog} N)$. The lower bound follows from Zang's recent theorem for rational-geometric sequences; our contribution is the matching upper bound. Thus one exact sequence connects self-supervised discovery, large-scale practical performance, and a substantial step below the classical $N^{4/3}$ bound for sparse practical Shellsort sequences.