X + Y sorting

Unsolved problem in computer science: Is there an ${\displaystyle X+Y}$ sorting algorithm faster than ${\displaystyle O(n^{2}\log n)}$? (more unsolved problems in computer science)

This problem can be solved using a straightforward comparison sort on the Cartesian product of the two given sets. When the sets have size ${\displaystyle n}$, their product has size ${\displaystyle n^{2}}$, and the time for a comparison sorting algorithm is ${\displaystyle O(n^{2}\log n)}$. This is the best upper bound known on the time for this problem. Whether ${\displaystyle X+Y}$ sorting can be done in a more slowly-growing time bound is an open problem.[3][2]

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}$. Although this can reduce the number of comparisons needed by a constant factor, compared to naive comparison sorting, they show 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, so additional information about the set ${\displaystyle X+Y}$ beyond this matrix ordering would be needed for any faster sorting algorithm.[1]

The numbers in the two input lists for the ${\displaystyle X+Y}$ sorting problem can be interpreted as Cartesian coordinates of a point in the ${\displaystyle 2n}$-dimensional space ${\displaystyle \mathbb {R} ^{2n}}$. If one partitions the space ${\displaystyle \mathbb {R} ^{2n}}$ into cells, so the set ${\displaystyle X+Y}$ has a fixed ordering within each cell, then the boundaries between these cells are hyperplanes defined by an equality of pairs ${\displaystyle x_{i}+y_{j}=x_{k}+y_{\ell }}$. The number of hyperplanes that can be determined in this way is ${\displaystyle {\tbinom {n}{2}}^{2}=O(n^{4})}$, and the number of cells that this number of hyperplanes can divide a space of dimension ${\displaystyle 2n}$ into is less than ${\displaystyle n^{8n}}$. Therefore, the set ${\displaystyle X+Y}$ has at most ${\displaystyle n^{8n}}$ different possible orderings.[1][4]

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 O(n²) 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 |\leq 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][5]

The first actual algorithm that achieves both ${\displaystyle O(n^{2})}$ comparisons and ${\displaystyle O(n^{2}\log n)}$ total complexity was published sixteen years later. The algorithm first recursively sorts the two sets ${\displaystyle X+X}$ and ${\displaystyle Y+Y}$, and uses 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. Then, it merges the two sets ${\displaystyle X-X}$ and ${\displaystyle Y-Y}$ and uses 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 splitting ${\displaystyle X}$ into two equal sublists ${\displaystyle A}$ and ${\displaystyle B}$, recursively sorting ${\displaystyle A+A}$ and ${\displaystyle B+B}$, inferring the ordering on ${\displaystyle A+B}$ as above, and merging the sorted results ${\displaystyle A+A}$, ${\displaystyle B+B}$, and ${\displaystyle A+B}$ together.[6]

On a RAM machine with word size w and integer inputs 0 ≤ {x, y} < n = 2^w, the problem can be solved in O(n log n) operations by means of the fast Fourier transform.[1]

Steven Skiena recounts a practical application in transit fare minimisation, an instance of the shortest path problem: given fares x and y for trips from departure A to some intermediate destination B and from B to final destination C, with only certain pairs of fares allowed to be combined, find the cheapest combined trip from A to C. Skiena's solution consists of sorting the pairs of fares 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. For this problem, one can use a priority queue of pairs, initialized to contain a single pair with the cheapest overall pair of fares. Then, when a pair ${\displaystyle (x,y)}$ is found to be disallowed, two more pairs formed by combining ${\displaystyle x}$ and ${\displaystyle y}$ with their successors in their respective sorted lists of single-hop fares can be added (if not already present) to the priority queue. 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.[3]

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.[7]

• 3SUM
• Integer sorting