Shellsort as Multi-Scale Relaxation: Learning Spectrum-Matched Gap Schedules

A Shellsort gap sequence is a multi-scale relaxation schedule. Each pass at gap $h$ eliminates inversions at length scale $h$, and the sequence cools the array from coarse to fine, analogous to a multigrid V-cycle or simulated-annealing schedule. This view suggests that the right gap sequence should depend on the input's *disorder spectrum*: the inversion rate measured across logarithmic strides. Classical sequences such as Ciura, Sedgewick, and Tokuda are instead fixed schedules, applying the same coarse-to-fine relaxation to every input. We test this spectrum-matching view by formulating gap selection as a Markov decision process whose state is the current disorder spectrum and whose action selects the next gap. A small PPO-trained policy improves comparison count by **15-16%** over Sedgewick across array sizes $N{=}128$ to $N{=}16{,}384$ on a seven-family input mixture, with training under 10 minutes on a consumer CPU. But the main value of the learned policy is not only that it improves Shellsort: it provides a probe into what effective gap schedules are doing. The learned schedules organize into three distinct relaxation regimes: gradual Brownian-like cooling for flat-spectrum inputs, faster Lévy-flight-like cooling for coarse-scale structure, and direct fine-scale relaxation for inputs whose disorder is already local. Spectrum statistics predict schedule statistics, training only on flat-spectrum inputs recovers a dense Ciura-like regime, and an ablation that replaces the adaptive policy with one global learned sequence reduces the gain from 15.6% to 0.9%. Input adaptivity, not the discovery of another static sequence, accounts for the gain. The marginal spectrum has blind spots: pipe-organ inputs share the random spectrum but their bipartite structure becomes visible only after the first pass, so sequential adaptation provides an additional margin. For known target distributions the policy can be used offline as a schedule compiler: run it on representative inputs, extract a per-distribution schedule, and hardcode that fixed sequence as a drop-in replacement for the existing static gaps with no neural runtime overhead. Together, these results recast Shellsort gap design as spectrum-matched scheduling.