Computing & AI · the experiment
Sorting without comparing everything
Candidates, references, a graph of allowed comparisons, and a bound that stood from 2011. Four questions, from beginner to expert, on how to sort when some pairs cannot be compared.
1 · The rule2 · Phases3 · QuickSort4 · Still open
1 · Spot what changes
Beginner
What makes generalized sorting different from ordinary sorting?
2 · Count the phases
Each phase of the algorithm sets a prediction for at least half of the links still pending and postpones the rest. A graph has about a million links, roughly 2²⁰.
Intermediate
About how many phases are needed, at most, before every link has a prediction?
3 · Find what breaks QuickSort
Expert
Why can't a QuickSort-style method simply be applied to generalized sorting?
4 · Spot what the paper does not give
Expert
Which of these does the paper not provide?
Order recovered
—