# 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](https://doi.org/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](https://doi.org/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](https://doi.org/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](https://doi.org/10.1007/s00453-012-9734-3), [arXiv:1212.4771](https://arxiv.org/abs/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](https://doi.org/10.1145/3285953), [arXiv:1705.01720](https://arxiv.org/abs/1705.01720)

## Source

Imported from [The Open Problems Project, Problem 41](https://topp.openproblem.net/p41), 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.