**Next:** Problem 42: Vertex-Unfolding Polyhedra

**Previous:** Problem 40: The Number of Pointed Pseudotriangulations

- Statement
Given two sets of numbers, each of size n, how quickly can the set of all pairwise sums be sorted? In symbols, given two sets X and Y, our goal is to sort the set X+Y = \{x+y \mid x \in X, y \in Y\}.

- Origin
The earliest known reference is Fredman [Fre76], who attributes the problem to Elwyn Berlekamp.

- Status/Conjectures
Open.

- Motivation
This is a simple special case of the more general question of

*sorting with partial information*: How many comparisons are required to sort if a partial order on the input set is already known? Hernández Barrera [Her96] and Barequet and Har-Peled [BHP01] describe several geometric problems that are “Sorting-(X+Y)-hard”. Specifically, there is a subquadratic-time transformation from sorting X+Y to each of the following problems: computing the Minkowski sum of two orthogonal-convex polygons, determining whether one monotone polygon can be translated to fit inside another, determining whether one convex polygon can be rotated to fit inside another, sorting the vertices of a line arrangement, or sorting the interpoint distances between n points in \R^d. (Although Barequet and Har-Peled [BHP01] claim only that the problems they consider are 3SUM-hard, their proofs immediately imply this stronger result.) Fredman also mentions an immediate application to multiplying sparse polynomials [Fre76].- Partial and Related Results
The obvious O(n^2 \log n)-time algorithm is also the fastest known. There are \Omega(n^2) lower bounds for this problem in various restrictions of the linear decision tree model of computation [Fre76], [Die89], [Eri99a]. The main problem is whether the logarithmic factor can be removed.

Fredman [Fre76] proved that if a given partial order on m elements has L linear extensions, then the set can be sorted in at most \log_2 L + 2m comparisons. For the sorting X+Y problem, we have m = n^2, the Hasse diagram of the partial order is an n\times n diagonal grid, and simple arguments about hyperplane arrangements imply that L = O(n^{8n}). Thus, Fredman’s algorithm can sort X+Y using only 8n\log n + 2n^2 comparisons; unfortunately, the algorithm needs exponential time to choose which comparisons to perform! This exponential overhead was reduced to polynomial time by Kahn and Kim [KK95] and then to O(n^2\log n) by Lambert [Lam92] and Steiger and Streinu [SS95]. These results imply that no superquadratic lower bound is possible in the full linear decision tree model.

If the input consists of n integers between -M and M, an algorithm of Seidel based on fast Fourier transforms runs in O(n + M\log M) time [Eri99a]. The \Omega(n^2) lower bounds require exponentially large integers.

A closely related problem does have a subquadratic solution: find a minimum element of X+Y, the so-called

*min-convolution*problem, posed by Jeff Erickson [DO06]. See [BCD+06] for the result and a discussion of connections to the sorting problem.- Related Open Problems
The decision version of this problem—does the set X+Y have n^2 unique elements?—is 3SUM-hard [BHP01]; see Problem 11.

- Categories
lower bounds

- Entry Revision History
E. Demaine, 6 June 2002; Jeff Erickson, 20 June 2002; J. O’Rourke, 20 Aug. 2006.

- [Her96]
A. Hernández Barrera. Finding an o(n^2 \log n) algorithm is sometimes hard. In

*Proc. 8th Canad. Conf. Comput. Geom.*, pages 289–294. Carleton University Press, Ottawa, Canada, 1996.- [BCD+06]
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, and Perouz Taslakian. Necklaces, convolutions, and X+Y. In

*Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006)*, page to appear, Zürich, Switzerland, September 11–13 2006.- [BHP01]
G. Barequet and S. Har-Peled. Polygon containment and translational min-Hausdorff-distance between segment sets are 3SUM-hard.

*Internat. J. Comput. Geom. Appl.*, 11:465–474, 2001.- [Die89]
M. Dietzfelbinger. Lower bounds for sorting of sums.

*Theoret. Comput. Sci.*, 66:137–155, 1989.- [DO06]
Erik D. Demaine and Joseph O’Rourke. Open problems from CCCG 2005. In

*Proc. 18th Canad. Conf. Comput. Geom.*, pages 75–80, 2006.- [Eri99a]
Jeff Erickson. Lower bounds for linear satisfiability problems.

*Chicago J. Theoret. Comput. Sci.*, 1999(8), 1999.- [Fre76]
M. L. Fredman. How good is the information theory bound in sorting?

*Theoret. Comput. Sci.*, 1:355–361, 1976.- [KK95]
Jeff Kahn and Jeong Han Kim. Entropy and sorting.

*J. Comput. Sys. Sci.*, 51:390–399, 1995.- [Lam92]
Jean-Luc Lambert. Sorting the sums (x_i+y_j) in O(n^2) comparisons.

*Theoret. Comput. Sci.*, 103:137–141, 1992.- [SS95]
W. Steiger and Ileana Streinu. A pseudo-algorithmic separation of lines from pseudo-lines.

*Inform. Process. Lett.*, 53:295–299, 1995.