# X + Y sorting

In computer science, ${\displaystyle {\boldsymbol {X}}+{\boldsymbol {Y}}}$ sorting is the problem of sorting pairs of numbers by their sum. It can be solved using a number of comparisons that is quadratic in the input length, fewer than would be needed needed to sort an unstructured list of equally many items. However, it is not known whether it is possible for an algorithm that solves the problem to have total running time faster by more than a constant factor than comparison sorting.

## Problem statement and history

Unsolved problem in computer science:

Is there an ${\displaystyle X+Y}$ sorting algorithm faster than ${\displaystyle O(n^{2}\log n)}$?

The input to the ${\displaystyle X+Y}$ sorting problem is two finite collections of numbers ${\displaystyle X}$ and ${\displaystyle Y}$, both of the same length. The problem's output is the collection of all pairs ${\displaystyle (x_{i},y_{j})}$ with ${\displaystyle x_{i}}$ in ${\displaystyle X}$ and with ${\displaystyle y_{j}}$ in ${\displaystyle Y}$, arranged into sorted order by the value of ${\displaystyle x_{i}+y_{j}}$ for each pair. One way to solve the problem would be to construct the Cartesian product of the two given sets (the collection of pairs to be sorted) and use this collection of pairs as the input to a standard comparison sorting algorithm such as merge sort or heapsort. When the input collections each consist of ${\displaystyle n}$ numbers, their Cartesian product consists of ${\displaystyle n^{2}}$ pairs, and the time for one of these comparison sorting algorithms to sort a collection of this many pairs is ${\displaystyle O(n^{2}\log n)}$. No asymptotically faster algorithm for ${\displaystyle X+Y}$ sorting is known. Whether it can be done in a faster time bound is an open problem,[1][2] posed by Elwyn Berlekamp prior to 1975.[3][2]

## Number of orderings

Together, the two input collections for the ${\displaystyle X+Y}$ sorting problem comprise ${\displaystyle 2n}$ numbers, which can alternatively be interpreted as the Cartesian coordinates of a point in the ${\displaystyle 2n}$-dimensional space ${\displaystyle \mathbb {R} ^{2n}}$. If one partitions this space ${\displaystyle \mathbb {R} ^{2n}}$ into cells defined by the property that the collection of pairs to be sorted has a fixed ordering within each cell, then each boundary between two cells lies within a hyperplane defined by an equality of pairs ${\displaystyle x_{i}+y_{j}=x_{k}+y_{\ell }}$, where ${\displaystyle (x_{i},y_{j})}$ and ${\displaystyle (x_{k},y_{\ell })}$ are two pairs whose ordering changes from one adjacent cell to the other. These hyperplanes are either generated by two disjoint pairs, or they have the simplified forms ${\displaystyle x_{i}=x_{k}}$ or ${\displaystyle y_{j}=y_{\ell }}$, so the number of distinct hyperplanes that can be determined in this way is

${\displaystyle k=2{\binom {n}{2}}^{2}+2{\binom {n}{2}}.}$
The number of cells that this number of hyperplanes can divide a space of dimension ${\displaystyle 2n}$ into is
${\displaystyle {\binom {k}{2n}}+{\binom {k}{2n-1}}+\cdots +{\binom {k}{0}}=O(n^{8n}).}$
Therefore, the set ${\displaystyle X+Y}$ has ${\displaystyle O(n^{8n})}$ different possible sorted orderings.[3][4][5]

Harper et al. (1975) suggest separately sorting ${\displaystyle X}$ and ${\displaystyle Y}$, and then constructing a two-dimensional matrix of the values of ${\displaystyle X+Y}$ that is sorted both by rows and by columns before using this partially-sorted data to complete the sort of ${\displaystyle X+Y}$. This idea can reduce the number of comparisons needed by a constant factor, compared to naive comparison sorting. However, they show that the number of possible orderings of a sorted matrix is large enough that any comparison sorting algorithm that can work for arbitrary ${\displaystyle n\times n}$ matrices that are sorted by rows and columns still requires ${\displaystyle \Omega (n^{2}\log n)}$ comparisons. Therefore, additional information about the set ${\displaystyle X+Y}$ beyond this matrix ordering would be needed for any faster sorting algorithm.[3]

The number of comparisons required to sort ${\displaystyle X+Y}$ is certainly lower than for ordinary comparison sorting: Michael Fredman showed in 1976 that ${\displaystyle X+Y}$ sorting can be done using only ${\displaystyle O(n^{2})}$ comparisons. More generally, he shows that any set of ${\displaystyle N}$ elements, whose sorted ordering has already been restricted to a family ${\displaystyle \Gamma }$ of orderings, can be sorted using ${\displaystyle \log _{2}|\Gamma |+O(N)}$ comparisons, by a form of binary insertion sort. For the ${\displaystyle X+Y}$ sorting problem, ${\displaystyle N=n^{2}}$, and ${\displaystyle |\Gamma |=O(n^{8n})}$, so ${\displaystyle \log _{2}|\Gamma |=O(n\log n)}$ and Fredman's bound implies that only ${\displaystyle O(n^{2})}$ comparisons are needed. However, the time needed to decide which comparisons to perform may be significantly higher than the bound on the number of comparisons.[4] If only comparisons between elements of ${\displaystyle X+Y}$ are allowed, then there is also a matching lower bound of ${\displaystyle \Omega (n^{2})}$ on the number of comparisons needed.[4][6]

The first explicit algorithm that achieves both ${\displaystyle O(n^{2})}$ comparisons and ${\displaystyle O(n^{2}\log n)}$ total complexity was published sixteen years later by Lambert (1992). The algorithm performs the following steps:

1. Recursively sort the two sets ${\displaystyle X+X}$ and ${\displaystyle Y+Y}$.
2. Use the equivalence ${\displaystyle x_{i}-x_{j}\leq x_{k}-x_{\ell }\Leftrightarrow x_{i}+x_{\ell }\leq x_{j}+x_{k}}$ to infer the sorted orderings of ${\displaystyle X-X}$ and ${\displaystyle Y-Y}$ without additional comparisons.
3. Merge the two sets ${\displaystyle X-X}$ and ${\displaystyle Y-Y}$ into a single sorted order, using a number of comparisons linear in their total size.
4. Use the merged order and the equivalence ${\displaystyle x_{i}+y_{j}\leq x_{k}+y_{\ell }\Leftrightarrow x_{i}-x_{k}\leq y_{\ell }-y_{j}}$ to infer the sorted order of ${\displaystyle X+Y}$ without additional comparisons.

The part of the algorithm that recursively sorts ${\displaystyle X+X}$ (or equivalently ${\displaystyle Y+Y}$) does so by the following steps:

1. Split ${\displaystyle X}$ into two equal sublists ${\displaystyle A}$ and ${\displaystyle B}$.
2. Recursively sort ${\displaystyle A+A}$ and ${\displaystyle B+B}$
3. Infer the ordering on ${\displaystyle A+B}$ using only the comparisons from a single merge step as above.
4. Merge the sorted results ${\displaystyle A+A}$, ${\displaystyle B+B}$, and ${\displaystyle A+B}$ together.

The number of comparisons ${\displaystyle C(n)}$ needed to perform this recursive algorithm on an input of ${\displaystyle n}$ items can be analyzed using the recurrence relation

${\displaystyle C(n)\leq 2C(n/2)+O(n^{2}),}$
where the ${\displaystyle 2C(n/2)}$ term of the recurrence counts the number of comparisons in the recursive calls to the algorithm to sort ${\displaystyle A+A}$ and ${\displaystyle B+B}$, and the ${\displaystyle O(n^{2})}$ term counts the number of comparisons used to merge the results. The master theorem for recurrence relations of this form shows that ${\displaystyle C(n)=O(n^{2})}$. The total time complexity is slower, ${\displaystyle O(n^{2}\log n)}$, because of the steps of the algorithm that use already-made comparisons to infer orderings of other sets. These steps can be performed in time ${\displaystyle O(n^{2}\log n)}$ by using a standard comparison-sorting algorithm with its comparison steps replaced by the stated inferences.[7]

## Non-comparison-based algorithms

Just as integer sorting can be faster than comparison sorting for small-enough integers, the same is true for ${\displaystyle X+Y}$ sorting. In particular, with integer inputs in the range from ${\displaystyle 0}$ to some upper limit ${\displaystyle M}$, the problem can be solved in ${\displaystyle O(n+M\log M)}$ operations by means of the fast Fourier transform.[3][2]

## Applications

Steven Skiena recounts a practical application in transit fare minimisation, an instance of the shortest path problem: find the cheapest two-hop airplane ticket between two given cities, from an input that describes the cost of each hop from the starting city or to the destination city, and describing which pairs of hops are allowed to be combined into a single ticket. Skiena's solution consists of sorting pairs of hops by their total cost as an instance of the ${\displaystyle X+Y}$ sorting problem, and then testing the resulting pairs in this sorted order until finding one that is allowed. To generate the sorted pairs in this order, Skiena uses a priority queue of pairs, initially containing only a single pair, the one consisting of the two cheapest hops. Then, when a pair ${\displaystyle (x,y)}$ is removed from the queue and found to be disallowed, two more pairs are added, with one of these two pairs combining ${\displaystyle x}$ with the next hop after ${\displaystyle y}$ in a sorted list of the hops to the destination, and the other pair combining ${\displaystyle y}$ with the next hop after ${\displaystyle x}$ in a sorted list of hops from the start. In this way, each successive pair can be found in logarithmic time, and only the pairs up to the first allowable one need to be sorted.[1]

## Related problems

Several other problems in computational geometry have equivalent or harder complexity to ${\displaystyle X+Y}$ sorting, including constructing Minkowski sums of staircase polygons, finding the crossing points of an arrangement of lines in sorted order by their ${\displaystyle x}$-coordinates, listing pairs of points in sorted order by their distances, and testing whether one rectilinear polygon can be translated to fit within another.[8]

The problem of testing whether two of the pairs in the ${\displaystyle X+Y}$ sorting problem have equal sums can be solved by sorting the pairs and then testing consecutive pairs for equality. In turn, it could be used to solve the 3SUM problem, implying that it is unlikely to have a strongly subquadratic algorithm.[2]

## References

1. ^ a b Skiena, Steven (2008). "4.4 War Story: Give me a Ticket on an Airplane". The Algorithm Design Manual (2nd ed.). Springer. pp. 118–120. doi:10.1007/978-1-84800-070-4_4.
2. ^ a b c d Demaine, Erik; Erickson, Jeff; O'Rourke, Joseph (20 August 2006). "Problem 41: Sorting X + Y (Pairwise Sums)". The Open Problems Project. Retrieved 23 September 2014.
3. ^ a b c d Harper, L. H.; Payne, T. H.; Savage, J. E.; Straus, E. (1975). "Sorting X + Y". Communications of the ACM. 18 (6): 347–349. doi:10.1145/360825.360869. MR 0378473.
4. ^ a b c Fredman, Michael L. (1976). "How good is the information theory bound in sorting?". Theoretical Computer Science. 1 (4): 355–361. doi:10.1016/0304-3975(76)90078-5. MR 0416100.
5. ^ Sloane, N. J. A. (ed.). "Sequence A343245". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
6. ^ Dietzfelbinger, Martin (1989). "Lower bounds for sorting of sums". Theoretical Computer Science. 66 (2): 137–155. doi:10.1016/0304-3975(89)90132-1. MR 1019082.
7. ^ Lambert, Jean-Luc (1992). "Sorting the sums (xi + yj) in O(n2) comparisons". Theoretical Computer Science. 103 (1): 137–141. doi:10.1016/0304-3975(92)90089-X. MR 1181041.
8. ^ Hernández Barrera, Antonio (1996). "Finding an o(n2 log n) algorithm is sometimes hard" (PDF). Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96). pp. 289–294.