Sorting X + Y: sorting all pairwise sums faster than n² log n

Given two lists of $n$ numbers, sort the $n^2$ sums of one number from each list. Sorting them from scratch takes $O(n^2\log n)$ time, yet only $O(n^2)$ comparisons are needed, and nobody knows how to turn that into a faster algorithm.

Problem

Let $X=\{x_1,\dots,x_n\}$ and $Y=\{y_1,\dots,y_n\}$ be sets of real numbers. Sorting $X+Y$ asks for the sorted order of the multiset

$$X+Y=\{\,x_i+y_j : 1\le i,j\le n\,\}.$$

Any general sorting algorithm does this in $O(n^2\log n)$ time.

Question. Can $X+Y$ be sorted in $o(n^2\log n)$ time, for example in $O(n^2)$ time, on the real RAM (or by an algorithm that accesses the inputs only through additions and comparisons)?

Background

The earliest reference is Fredman (1976), who attributes the problem to Elwyn Berlekamp [1]. It is the simplest case of sorting with partial information: the order of $X+Y$ is heavily constrained by the orders of $X$ and $Y$, so far fewer comparisons are needed than for $n^2$ arbitrary numbers. Several geometric problems are at least as hard, among them sorting the vertices of a line arrangement, sorting all pairwise distances of a point set, and computing Minkowski sums of orthogonally convex polygons, and Fredman noted an application to multiplying sparse polynomials. The decision version, whether all $n^2$ sums are distinct, is 3SUM-hard.

What is known

• Few comparisons suffice. Fredman (1976) showed that $8n\log n+2n^2$ comparisons suffice, but choosing them took exponential time [1]. Lambert (1992) and Steiger and Streinu (1995) gave algorithms that use $O(n^2)$ comparisons and $O(n^2\log n)$ total time [2], [3]. Kane, Lovett and Moran (2019) built comparison-based decision trees that sort $X+Y$ with a near-linear number of comparisons, optimal up to polylogarithmic factors [5].
• Lower bounds. $\Omega(n^2)$ lower bounds hold in restricted linear decision tree models (Fredman; Dietzfelbinger, 1989; Erickson, 1999), but by the results above no superquadratic bound is possible in the full linear decision tree model.
• Special inputs. For integers in $[-M,M]$, Seidel's algorithm based on the fast Fourier transform runs in $O(n+M\log M)$ time.
• Neighbours of the problem. $(\min,+)$ and $(\mathrm{median},+)$ convolution, which compute order statistics along the antidiagonals of the $X+Y$ matrix, can be solved in $o(n^2)$ time [4].

What would count as progress

• An algorithm that sorts $X+Y$ in $o(n^2\log n)$ time, with a proof of correctness and running time; its output on any input can be checked in $O(n^2)$ time.
• An $o(n^2\log n)$ algorithm for one of the problems known to be at least as hard as sorting $X+Y$.
• A lower bound of $\omega(n^2)$ in a natural model that accounts for the cost of choosing comparisons.

References

1. M. L. Fredman, How good is the information theory bound in sorting?, Theoret. Comput. Sci. 1 (1976), 355–361. doi:10.1016/0304-3975(76)90078-5
2. J.-L. Lambert, Sorting the sums $(x_i+y_j)$ in $O(n^2)$ comparisons, Theoret. Comput. Sci. 103 (1992), 137–141. doi:10.1016/0304-3975(92)90089-X
3. W. Steiger and I. Streinu, A pseudo-algorithmic separation of lines from pseudo-lines, Inform. Process. Lett. 53 (1995), 295–299. doi:10.1016/0020-0190(94)00201-9
4. D. Bremner, T. M. Chan, E. D. Demaine, J. Erickson, F. Hurtado, J. Iacono, S. Langerman, M. Pătraşcu and P. Taslakian, Necklaces, convolutions, and $X+Y$, Algorithmica 69 (2014), 294–314. doi:10.1007/s00453-012-9734-3, arXiv:1212.4771
5. D. M. Kane, S. Lovett and S. Moran, Near-optimal linear decision trees for $k$-SUM and related problems, J. ACM 66 (2019); STOC 2018. doi:10.1145/3285953, arXiv:1705.01720

Source

Imported from The Open Problems Project, Problem 41, curated by Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.