Papex

Open problem · Computer science · Open

X + Y sorting

Can all pairwise sums of two lists of n numbers be sorted faster than the O(n² log n) time of ordinary sorting?

Summary

Only O(n²) comparisons are needed to sort the n² sums x + y, yet no algorithm is known to beat general-purpose sorting in total running time. The question was posed by Elwyn Berlekamp before 1975.

Why it is open

The obvious algorithm forms the n² sums and sorts them in O(n² log n) time. The Open Problems Project, a list of open problems in computational geometry and related fields, records it as the fastest known in an entry last revised in 2006, and later papers still describe the question as open [3, 6, 8]. The earliest known reference is a 1976 paper by Michael Fredman [1], who, according to the Open Problems Project, attributes the problem to Elwyn Berlekamp [8].

Counting comparisons and counting time give different answers here [3, 6]. Fredman showed that O(n²) comparisons suffice in the nonuniform linear decision tree model, in which each step tests the sign of a linear combination of the inputs and the work of choosing the next test is not counted [2, 3, 8]. It remains open whether this can be turned into an O(n²)-time algorithm on the real RAM [3], an idealised machine that, in the version used by Allan Grønlund and Seth Pettie, adds and compares real numbers in one step each [4]. Jeff Erickson called closing this logarithmic gap, even for X + Y, "a long-standing and apparently very difficult open problem" [2].

A resolution would be an algorithm that sorts X + Y in o(n² log n) time, or a proof that algorithms of a stated kind cannot. The Open Problems Project frames the main problem as whether the logarithmic factor can be removed [8]. The model of computation matters. For n integers between −M and M, an algorithm of R. Seidel based on fast Fourier transforms runs in O(n + M log M) time, while the known Ω(n²) lower bounds require exponentially large integers [8]. Describing the same technique for a related problem, Erickson notes that Seidel's algorithm "cannot be modeled even as an algebraic decision tree" [2]. No prize or committee sets further terms; the status here follows Wikipedia's list of unsolved problems in computer science [9].

What is known

Few comparisons (1976–1999). Fredman proved that m elements whose sorted order is known to be one of L possible orders can be sorted with at most log₂ L + 2m comparisons [4, 8]. For X + Y, m = n² and arguments about hyperplane arrangements give L = O(n^(8n)), so his method needs only 8n log n + 2n² comparisons, but exponential time to decide which comparisons to make [8]. Daniel Kane, Shachar Lovett and Shay Moran point out that so few possible orders would, from an information-theoretic perspective, allow O(n log n) comparisons; yet Fredman's bound of Θ(n²) is tight when only comparisons between two sums are allowed [5]. Fredman's Ω(n²) lower bound also covers deciding whether X + Y contains a repeated element [2]. Martin Dietzfelbinger generalised it in 1989 to an Ω(n^(r/2)) lower bound for deciding whether two disjoint subsets of size r/2 have the same sum, and Erickson in 1999 extended Fredman's bound to arbitrary 4-linear decision trees, in which each test is the sign of a linear combination of at most four inputs [2].

Explicit algorithms (1992–1995). The exponential overhead was later reduced to polynomial time by Jeff Kahn and Jeong Han Kim, and to O(n² log n) by Jean-Luc Lambert and by William Steiger and Ileana Streinu [8]. Steiger and Streinu's divide-and-conquer algorithm sorts X + Y in O(n² log n) time with only O(n²) comparisons; the extra log n in its running time is "the result of repeating the same queries several times", Erickson writes [2]. These algorithms imply that no lower bound above quadratic is possible in the full linear decision tree model [8].

Richer queries (2017–2019). Kane, Lovett and Moran showed that X + Y can be sorted with O(n log² n) queries if each query may compare two differences of sums, (xᵢ + yⱼ) − (xᵢ′ + yⱼ′) against (xₖ + yₗ) − (xₖ′ + yₗ′); every query uses at most eight inputs with coefficients −1, 0 or 1 [5]. Their construction rests on "inference dimension", a notion the same authors introduced for active classification with comparison queries [5]. Haim Kaplan, László Kozma, Or Zamir and Uri Zwick called this "a breakthrough result" and noted that it is not known how to implement the algorithm efficiently [6].

Easier relatives. Single order statistics are much easier: Donald B. Johnson with Tetsuo Mizoguchi, and Johnson with Samuel D. Kashdan, showed that the median of X + Y can be found in O(n log n) time [6]. David Bremner and eight co-authors showed that (min,+) convolution amounts to finding the minimum on each antidiagonal of the X + Y matrix, and (median,+) convolution its median, and gave o(n²)-time algorithms for both on the real RAM [3]. Timothy Chan later shaved further logarithmic factors from (median,+) convolution [7].

3SUM and Fredman's trick (2014–2020). The 3SUM problem asks whether any three of n real numbers sum to zero, and a conjecture that it needs about n² time was used to derive Ω(n²) lower bounds for numerous geometric problems [4]. The Open Problems Project lists deciding whether X + Y has n² distinct elements as 3SUM-hard [8]. In 2014 Grønlund and Pettie refuted the conjecture: 3SUM has decision-tree complexity O(n^(3/2) √(log n)) and slightly subquadratic algorithms [4]. Their algorithms "borrow liberally" from Fredman's 1976 work, including what they call Fredman's trick, that a + b is less than c + d exactly when a − c is less than d − b [4]. Chan reduced the time for 3SUM on n real numbers to O((n²/log² n)(log log n)^O(1)) [7], and Kane, Lovett and Moran solved k-SUM, for any constant k, with linear decision trees of O(n log² n) queries [5].

Main approaches

Realising Fredman's bound. Choose O(n²) informative comparisons quickly enough that the total time drops below n² log n [3]. Strongest evidence: explicit algorithms that make only O(n²) comparisons and run in O(n² log n) time [2, 8]. Main difficulty: the remaining log n comes from repeated queries, and Erickson describes closing the gap as apparently very difficult [2].

Richer decision trees. Allow queries on several sums at once and bound their number using inference dimension [5]. Strongest evidence: O(n log² n) queries for X + Y and for k-SUM [5]. Main difficulty: no efficient implementation is known [6], and the queries still leave a log n factor above the bound that Kane, Lovett and Moran conjecture [5].

Structure of the antidiagonals. Exploit order statistics on the antidiagonals of the X + Y matrix [3]. Strongest evidence: subquadratic (min,+) and (median,+) convolution [3, 7], using a geometric domination technique of Chan that Grønlund and Pettie also apply to 3SUM [4]. Main difficulty: Bremner and colleagues leave open whether this information leads to o(n² log n) sorting, and expect that further improvements to their convolution algorithms would require progress on, or have implications for, all-pairs shortest paths [3].

Lower bounds in restricted models. Close the gap from below by proving lower bounds for restricted kinds of algorithm [2, 8]. Strongest evidence: Ω(n²) for 4-linear decision trees [2]. Main difficulty: no superquadratic bound is possible in the full linear decision tree model [8], richer queries need only O(n log² n) [5], and the Ω(n²) bounds rely on exponentially large integers [8].

Open sub-questions

  1. Repeated queries. Can the queries that Steiger and Streinu's algorithm repeats be shared, so that it runs in o(n² log n) time on the real RAM while keeping O(n²) comparisons [2, 8]?
  2. Fewer queries. Is there a linear decision tree that sorts X + Y with O(n log n) queries, each involving at most four inputs, as Kane, Lovett and Moran conjecture [5]?
  3. Building the tree. Can the O(n log² n)-query decision tree of Kane, Lovett and Moran be constructed and run in o(n² log n) total time [5, 6]?
  4. From antidiagonals to order. Do the minima and medians of all antidiagonals, computable in o(n²) time, shorten the time needed to sort the whole X + Y matrix [3]?
  5. Size of hard inputs. Do Ω(n²) comparison lower bounds hold for integer inputs of polynomially many bits, between the exponentially large adversary inputs now used and the small integers handled by Seidel's algorithm [2, 8]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Fredman, M. L. (1976). How good is the information theory bound in sorting? Theoretical Computer Science 1(4), 355–361. 10.1016/0304-3975(76)90078-5 · Checked 16 Oct 2026
  2. Erickson, J. (1999). Lower bounds for linear satisfiability problems. Chicago Journal of Theoretical Computer Science 1999, article 8. 10.4086/cjtcs.1999.008 · Checked 16 Oct 2026
  3. Bremner, D., Chan, T. M., Demaine, E. D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., Pătraşcu, M. & Taslakian, P. (2014). Necklaces, convolutions, and X+Y. Algorithmica 69(2), 294–314 (published online 2012); conference version in ESA 2006. 10.1007/s00453-012-9734-3 · Checked 16 Oct 2026
  4. Grønlund, A. & Pettie, S. (2018). Threesomes, degenerates, and love triangles. Journal of the ACM 65(4), 1–25; conference version in FOCS 2014. 10.1145/3185378 · Checked 16 Oct 2026
  5. Kane, D. M., Lovett, S. & Moran, S. (2019). Near-optimal linear decision trees for k-SUM and related problems. Journal of the ACM 66(3), 1–18; conference version in STOC 2018. 10.1145/3285953 · Checked 16 Oct 2026
  6. Kaplan, H., Kozma, L., Zamir, O. & Zwick, U. (2019). Selection from heaps, row-sorted matrices, and X+Y using soft heaps. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019), OASIcs 69, 5:1–5:21. 10.4230/OASIcs.SOSA.2019.5 · Checked 16 Oct 2026
  7. Chan, T. M. (2020). More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems. ACM Transactions on Algorithms 16(1), 1–23 (published online 2019); conference version in SODA 2018. 10.1145/3363541 · Checked 16 Oct 2026
  8. Demaine, E. D., Mitchell, J. S. B. & O'Rourke, J. (eds.). Problem 41: Sorting X+Y (pairwise sums). The Open Problems Project; entry by E. Demaine, J. Erickson and J. O'Rourke, last revised 20 August 2006. Source · Checked 16 Oct 2026
  9. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 16 Oct 2026

Page reviewed 16 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Computing