In-place sorting uses O(1) extra memory. Adaptive sorting exploits existing order — if the input is almost sorted, don't pay for a full sort. Achieving both simultaneously has been an open problem. Standard in-place sorts (heapsort) ignore existing order. Standard adaptive sorts (natural mergesort) use O(n) extra memory for merging.
Munro & Wild (arXiv:2603.05676) solve both: a strictly in-place mergesort that runs in O(n(1+H)) time, where H is the entropy of the run structure. If the input has few runs (near-sorted), H is small and the algorithm is fast. If the input is random, H is log n and the algorithm matches heapsort. The title — “How to Sort in a Refrigerator” — refers to sorting in severely memory-constrained environments.
The technique: natural mergesort identifies existing sorted runs in the input. The challenge is merging two runs without a buffer. Previous in-place merge algorithms exist but are complex and slow. The key insight is that you don't need to merge perfectly — you can merge approximately, leaving small unsorted regions that are cleaned up in a second pass. The approximate merge uses rotation: physically moving blocks of elements within the array to interleave two runs, using only O(1) tracked pointers.
The entropy H measures how much information the sort actually needs to discover. An array with two long runs has H ≈ 1 — you just need to find the boundary and merge. An array that's already sorted has H = 0 — you scan once and stop. A random array has H ≈ log n — every element's position must be determined.
The optimality is information-theoretic. No comparison-based sort can do better than Ω(n(1+H)) on inputs with run entropy H. The algorithm matches this bound while using no extra memory. It's not just fast for nearly sorted inputs — it's provably as fast as physically possible for any degree of existing order.