Computing & AIPreprintTheory3 min read

SORTING WITH FORBIDDEN COMPARISONS, NEARLY AS FAST

To put n items in order by comparing them two at a time, about n log n comparisons are both necessary and enough — log n, the logarithm, grows very slowly: roughly the number of times n can be halved before reaching 1. But that assumes any two items can be compared.

Often they cannot. The authors borrow an example from a 2011 paper: several candidates apply for the same job, each with references. Two candidates can be compared only if some reference knows both of them. The comparisons allowed form a network, a graph: each item is a point, each permitted comparison a link. The true order is hidden, but the graph is guaranteed to contain it, as a path linking each item to the next. The question: how many comparisons does it take to recover the order? This is generalized sorting.

Why the usual tricks fail

The classic algorithms rely on freedom of choice. QuickSort picks a “pivot” and compares it with most other items, but an arbitrary graph may have no item linked to most others. MergeSort splits the items into groups and sorts each one, but a group may not be sortable on its own: two items that are neighbours in the final order need not be linked within it. More fundamentally, ordinary sorting always has a comparison available that rules out a good share of the possible orders; with restricted comparisons, there may be none.

Progress was slow. In 2011, Zhiyi Huang, Sampath Kannan and Sanjeev Khanna found a method using about n¹·⁵ comparisons, up to logarithmic factors, and that bound stood for arbitrary graphs ever since. They even asked whether the problem might be fundamentally harder than ordinary sorting, needing n raised to a power above 1.

Predict first, repair later

Sanjeev Khanna, of New York University, Aaron Putterman, of Harvard University, and Junkai Song, also of New York University, now answer that question: no. Their randomised algorithm, which makes random choices along the way, sorts with about n log⁴ n comparisons on average, on any graph — only a few logarithmic factors above ordinary sorting. And, they write, it is “relatively simple”. The gain is theoretical, though: the proof’s constants are enormous (factors such as 2³²), so the advantage only shows for very large n.

It builds on a known result: if someone hands you a guess, for every link, of which of its two items comes first, wrong on w of them, the order can be recovered with about n log n + w comparisons. So the task becomes producing a guess with few errors using few comparisons. The key steps:

  • A rough first guess. Compare a random sample of linked pairs and pick any order consistent with the answers. It makes many errors, but not too many.
  • Isolate the errors, rather than fix them. Instead of correcting wrong guesses, the algorithm finds parts of the graph where errors are denser than average and sets them aside. Each round cuts the remaining errors, in expectation, by a factor of four.
  • Come back later. The links set aside are handled in a later phase. Each phase settles at least half of the links still pending, so the number of phases grows only like the logarithm of the number of links: a million links, about 2²⁰, need about twenty.

A proof found with machines

The paper’s AI disclosure is unusually detailed. It states that ChatGPT 6-Astra “was essential in proving the improved bounds”. A model first found an algorithm using about n¹·³³ comparisons, then stalled. The authors pushed it to n¹·²; then, prompted dozens of times over several weeks, models found successive improvements — n^(10/9), n^(17/16), n^(19/18) — before reaching the near-linear algorithm. The authors add that it is unclear whether their own intermediate step was essential to that final discovery.

What is still open

The result counts comparisons, not computing time: as stated, the algorithm does not run in polynomial time: it uses few comparisons, but its computing time explodes as n grows, because at one step it tries every possible ordering of a set of items. The 2011 method had no such problem. The authors list three open questions: whether the remaining logarithmic factors can be removed, whether an algorithm without randomness can do as well, and whether an efficient algorithm can reach the same number of comparisons — or even beat n¹·⁵ at all.