Why Can't AI Sort?

10 Sep, 2026

Sorting is a solved problem, yet language models can still drop items, misorder lists, or change answers when irrelevant details change. Sorting offers a simple test of AI reliability.

RolandH, Heapsort sorting a randomized array, 2006. CC BY SA 3.0, via Wikimedia Commons.

Long ago when I helped write a sorting routine for BSD Unix, the hard part was shaving comparisons off an inner loop. The operating systems that inherited its descendant now run on machines capable of generating working software, explaining quantum field theory, and summarizing a filing cabinet before you finish reading the first page. Recently I have been putting a much smaller question to them. Can you put these six numbers in order?

[17, 4, 23, 4, -2, 10]

Any competent sorting routine returns [-2, 4, 4, 10, 17, 23], and returns it every time, on every machine, for as long as the machine runs. Language models usually return it too, so the interesting question is not whether they can sort. It is what happens when you change the problem in ways that cannot possibly change the answer.

That question closes this series on algorithms as the quiet machinery underneath ordinary life. The first entry, I Weigh How Much?, was about a bathroom scale deciding which of its own measurements to believe, and the second, I Found My Name in macOS, was about why a programmer picks one sorting algorithm over another and what it means that a choice made in 1991 still survives in the source code of a modern operating system. The third is about sorting becoming something it was never meant to be, which is an instrument for measuring a technology that did not exist when the algorithms were written.

The virtue of not understanding

Heapsort has no opinion about the list it is given. It does not notice that one number is the sum of two others, does not wonder whether a minus sign was a typo, and does not decide that "three" should follow "two" because that is how counting works. It performs comparisons with the function it was handed and rearranges an array accordingly, and the comments we wrote in 1991 promise exactly two things: bounded work in the worst case, and essentially no extra memory. Nothing in that file can be distracted, because nothing in it is capable of interest.

A language model works the other way around. Its power comes from reading meaning, context, and intent, which is why it can summarize a policy memo or find the bug in someone else's code, and those same capacities turn into liabilities the moment a task becomes rigidly mechanical. The paradox is worth holding onto for the rest of this piece. Classical sorting works partly because the computer does not understand the list, and a language model can fail partly because it does.

A benchmark made of lists

Steffen Herbold, at the University of Passau, built a benchmark on precisely that intuition in April 2025. SortBench generates lists, asks a model to sort them with a plain instruction and no prompt engineering, and grades the result. Lists double in length from two items up to 256, ten at each size, running from ordinary integers and English words through negative numbers, tightly clustered floats, random strings, and words spelled out as numbers. Seven models saw 1,440 lists apiece.

The grading is the clever part, because Herbold scores three things separately: whether the output is a parseable list at all, whether the ordering is correct, and whether the returned items are still the items that went in. He calls the last one faithfulness, and it is the idea worth taking from the whole exercise. Picture a model handed 100 values that returns them in flawless ascending order, having quietly dropped two, repeated a third, and lost a minus sign on the way. The output is beautifully sorted and is not a sorting of your list. Faithfulness fell across the board as lists grew, and the diagnostic tasks were sharper still: given a list already in order, so that the job reduces to handing it back unchanged, the models typically still did not manage it perfectly. The failure has nothing to do with sorting. It is a failure to pass 256 items through a system intact.

The prettiest failure came from number words. Python orders strings by their characters, so sorted(["one", "two", "three"]) gives one, three, two, and the first ten number words come out as eight, five, four, nine, one, seven, six, ten, three, two. A model knows perfectly well what those words mean, and that knowledge is the trap. Herbold found that the strongest reasoning model in his set frequently recognized the strings as numbers, converted them, sorted the integers, and returned numerals, which is a correct answer to a question nobody asked. Models without reasoning at inference time did not make that mistake. In the open reasoning traces, one model went hunting for an equation that would describe the list as a sequence, and another stated correctly at the outset that the task required lexicographic ordering and then sorted by numeric value anyway.

Extra reasoning did not reliably help, and was sometimes the mechanism of failure: the outputs that could not be parsed at all had by far the longest reasoning traces, because a model that keeps repeating a list to check itself has many more chances to lose an item. The lesson is not that reasoning models are bad. It is that reasoning and reliability are different properties, and a system can spend more computation on a problem and end further from the constraint it was required to respect. Two cautions belong here. SortBench version 1.0 tested a 2025 lineup and was designed for yearly regeneration so it would not leak into training data, so those rankings are history rather than a scoreboard, and short lists did little to distinguish the strongest models, with the clearest separation emerging at 256 items. A system that handles ten records correctly has told you nothing about how it handles 500.

Change something that should not matter

Here is what makes sorting useful rather than merely embarrassing. Take the list above and shuffle it into [4, 10, -2, 23, 17, 4]. Same values, same correct answer. Present the input in reverse order. Add 100 to every element, which shifts the values and preserves every ordering relationship among them. Add a second 4, and the answer is the original plus exactly one more 4. Each transformation has a known effect on the correct output, which is what makes the family worth running: five prompts built from one list tell you more than five unrelated questions, because you have stopped checking whether an answer is right and started checking whether a relationship holds.

Models are demonstrably sensitive to exactly this kind of irrelevance. Tang and colleagues showed at NAACL in 2024 that listwise rankings depend on the order in which candidates are presented, and that shuffling the input repeatedly and aggregating the results improved ranking scores substantially, by as much as 52% in their experiments. Pezeshkpour and Hruschka found the same shape of problem in multiple choice questions, where moving the options moves the answer. Ranking is not sorting and the parallel should not be pushed further than it goes, but sorting is the cleaner instrument because the correct output is known before you start. Software testing has a name for the method. Metamorphic testing evaluates a system you cannot fully specify by applying transformations whose effect you can specify, and researchers have begun applying it to language models. The plain version is the one to keep: change something that should not matter, and see whether the answer changes.

What you count changes whether you can count it

In January 2026 a group at Jena took that principle to its most austere form. Martiño Ríos-García, Nawaf Alampara, and Kevin Jablonka built a benchmark called WhatCounts that does nothing but count items in a clean, delimited list, with no duplicates, no distractors, and no ambiguity about where one item ends. The only thing that varies is what the items are: addresses, chemicals, cities, people's names, phone numbers, or symbols. Accuracy varied by more than 40% on that basis alone.

The authors then spent most of the paper trying to explain the gap away and failed. Equalizing tokens rather than items generally widened it, naming the separator in the prompt did nothing, and wrapping every item in XML tags did nothing either, though the models proved better at identifying items than at counting them, which puts the failure in the aggregation rather than the perception. Turning up the reasoning effort left accuracy roughly flat and made the gap wider. Fine-tuning a base model on 60,000 rows of unrelated preference data scrambled which categories it could count without moving its score on a conventional math benchmark. Two findings deserve to be uncomfortable. The better a model performed on average, the larger its gap, so the fragility grew with capability instead of shrinking, and when the same models were put in an agent loop with a Python execution tool available, so that counting was one line away, accuracy improved and the gap between categories got wider. Their conclusion is blunt enough to quote: "What you count changes whether you can count it." Models do not implement algorithms, on this account. They approximate them, and the approximation depends on its arguments.

The guarantee is the product

Here is why a Chief Data Officer should care about a benchmark made of six numbers. The value of heapsort was never speed, since it is usually the slowest of the three sorts in the BSD library. Its value was a promise that held regardless of input: bounded work in the worst case, a fixed amount of memory, every element preserved. A standard library ships guarantees, and a generative system ships answers, which is a much weaker thing to receive, because an answer can be inspected only for whether it looks right.

Institutions now hand these systems the work that sorting miniaturizes: ranking applicants, reconciling two record systems, pulling figures from a report, deduplicating a roster, summarizing a file. Fluency hides the errors, because a dropped row does not announce itself in prose, and a ranking that depends on the order the candidates arrived in looks identical to one that does not. Reviewing outputs one at a time cannot detect the absence of a guarantee, since each output may be perfectly fine on its own terms. The only way to learn whether a behavior is stable is to vary what should not matter and watch, and that is a governance practice rather than a technical curiosity. None of it settles anything about intelligence, and the temptation to make it do so should be resisted. A model that violates a sorting invariant has not been shown to be stupid, and a model that sorts 256 items has not been shown to reason. Sorting earns its place in the argument precisely because those questions can be left alone: we know the required answer, we can transform the input in controlled ways, and we can check whether what must stay true stayed true.

More than 30 years ago the question was how to make a machine put things in order quickly and correctly, and the answer was written into a library that has needed almost no revision since. Nobody needs a better sorting algorithm. What we need is a task small enough to state in a sentence, with a right answer nobody can argue about, that can be run again and again against systems whose answers are getting harder to check. The old reliable thing turns out to have a second use. I once worked on how machines sort, and I am now more interested in what happens when they do not.

Further Reading

From this blog

• I Weigh How Much? - the first entry, on the judgments a bathroom scale's firmware makes before it shows you a number.
• I Found My Name in macOS - the second entry, on heapsort, engineering tradeoffs, and the longevity of foundational code.

Sources

• Herbold, S. (2025). SortBench: Benchmarking LLMs based on their ability to sort lists. arXiv:2504.08312. Source of the validity, sorting, and faithfulness scores, the number-word results, the overthinking analysis, and the list-length findings.
• Ríos-García, M., Alampara, N., and Jablonka, K. M. (2026). Semantic Content Determines Algorithmic Performance. arXiv:2601.21618. The WhatCounts benchmark, the semantic gap, the ablations, and the agentic results.
• Tang, R., Zhang, C., Ma, X., Lin, J., and Ture, F. (2024). Found in the Middle: Permutation Self-Consistency Improves Listwise Ranking in Large Language Models. NAACL 2024, 2327-2340.
• Pezeshkpour, P., and Hruschka, E. (2024). Large Language Models Sensitivity to The Order of Options in Multiple-Choice Questions. Findings of NAACL 2024, 2006-2017.
• heapsort.c, Apple Libc, stdlib/FreeBSD - the file discussed in the previous entry, with the 1991 and 1993 Berkeley copyright and the Knuth citations.

#AIData #Algorithms