Sorting is the most studied problem in computing and the small cases are the most studied part of it. Sorting three items is not an interesting algorithmic question. It is, however, an interesting engineering question, because every large sort bottoms out in small ones and those small routines run constantly.
In 2023 DeepMind published AlphaDev in Nature. It treats writing assembly as a single-player game: each move adds one machine instruction, and the score rewards programs that are correct and short. Played enough times, it found sorting routines for three, four and five elements that were shorter than the ones in the standard library.
Those routines went into LLVM's libc++. It was the first change to that part of the sorting library in over a decade, and the first time an algorithm designed by reinforcement learning was added to it. The reported gains were up to 70 per cent for sequences of length five and about 1.7 per cent for sequences over 250,000.
What it did not do
This is the part that gets garbled. AlphaDev did not beat the theoretical limits of sorting, and it did not reduce the number of comparisons.
There is a hard floor on comparison sorting that comes from counting rather than cleverness. A list of n items has n factorial orderings, each comparison splits the possibilities in two, so you need at least log base 2 of n factorial comparisons to tell them apart. For five items that is 7. The sorting comparisons calculator works it out for any size, and the thing it shows most clearly is that the good algorithms are already close: merge sort spends 8,977 comparisons on a thousand items against a floor of 8,530.
AlphaDev left all of that untouched. What it found was that the same comparisons can be expressed in fewer machine instructions, including a move it discovered where two operations collapse into one. That is an optimisation below the level the floor describes, which is why it can be a genuine improvement without contradicting a theorem.
Why small cases are worth this much effort
Because of where they sit. Library sorts switch to a simple method below some size, so the three, four and five element routines are the base case of nearly every sort that runs anywhere. A few instructions saved there is multiplied by an enormous number of calls.
It is also a well-shaped problem for a search. The space of short instruction sequences is large but finite, correctness is checkable exactly, and the score is a number. That is the same shape as the problems in the FunSearch bin packing work: not proving something, but finding an object in a space where an evaluator can tell you immediately whether you have improved.
The floor itself is not always reachable, incidentally. For twelve items the counting argument says 29 comparisons but 30 are genuinely needed, and that is the smallest case where the bound is provably out of reach.