We consider the problem of sorting n items, given the outcomes of m pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\textrm{O}(m+\log T)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>O</mtext> <mo stretchy="false">(</mo> <mi>m</mi> <mo>+</mo> <mo>log</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time and does <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\textrm{O}(\log T)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>O</mtext> <mo stretchy="false">(</mo> <mo>log</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> comparisons, where T is the number of total orders consistent with the pre-existing comparisons. Our running time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been studied intensely since 1976 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\textrm{O}(\log T)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>O</mtext> <mo stretchy="false">(</mo> <mo>log</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> on the number of comparisons has a time bound of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\textrm{O}(n^{2.5})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>O</mtext> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mn>2.5</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and is more complicated. Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient search in a sorted list. It outputs the items in sorted order one by one. It can be modified to stop early, thereby solving the important and more general top-k sorting problem: Given k and the outcomes of some pre-existing comparisons, output the smallest k items in sorted order. The modified algorithm solves the top-k sorting problem in minimum time and comparisons, to within constant factors.

Fast and Simple Sorting Using Partial Information

期刊论文
发表日期：

2026年5月5日

查看全文

Bernhard Haeupler,
Richard Hladík,
John Iacono,
Václav Rozhoň,
Robert E. Tarjan,
Jakub Tětek

摘要

We consider the problem of sorting n items, given the outcomes of m pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in $\textrm{O}(m+\log T)$ $O (m + log T)$ time and does $\textrm{O}(\log T)$ $O (log T)$ comparisons, where T is the number of total orders consistent with the pre-existing comparisons. Our running time and comparison bounds are best possible up to constant factors, thus resolving a problem that has been studied intensely since 1976 (Fredman, Theoretical Computer Science). The best previous algorithm with a bound of $\textrm{O}(\log T)$ $O (log T)$ on the number of comparisons has a time bound of $\textrm{O}(n^{2.5})$ $O (n^{2.5})$ and is more complicated. Our algorithm combines three classic algorithms: topological sort, heapsort with the right kind of heap, and efficient search in a sorted list. It outputs the items in sorted order one by one. It can be modified to stop early, thereby solving the important and more general top-k sorting problem: Given k and the outcomes of some pre-existing comparisons, output the smallest k items in sorted order. The modified algorithm solves the top-k sorting problem in minimum time and comparisons, to within constant factors.