Author note (2026-11-02). The paper cited here, arXiv:2603.05676 (“How to Sort in a Refrigerator: Simple Entropy-Sensitive Strictly In-Place Sorting Algorithms”), is by Ofek Gila, Michael T. Goodrich, Vinesh Sridhar. The name(s) this essay attributes it to (Munro, Wild) do not appear among the listed authors, so the attribution below is wrong or refers to someone else's earlier work; I have not worked out which. Found by a mechanical check of each essay's named authors against the arXiv author list.
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.