X + Y sorting

Short description: Problem of sorting pairs of numbers by their sum

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

Geometric visualization of the [math]\displaystyle{ X+Y }[/math] sorting problem. The input sets [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] are represented by the sets of vertical and horizontal black lines (respectively), and the goal of the problem is to sort the crossing points by the positions of the red diagonal lines through them.

In computer science, [math]\displaystyle{ \boldsymbol{X}+\boldsymbol{Y} }[/math] sorting is the problem of sorting pairs of numbers by their sums. Applications of the problem include transit fare minimisation, VLSI design, and sparse polynomial multiplication. As with comparison sorting and integer sorting more generally, algorithms for this problem can be based only on comparisons of these sums, or on other operations that work only when the inputs are small integers.

It is unknown whether this problem has a comparison-based solution whose running time is asymptotically faster than sorting an unstructured list of equally many items. Therefore, research on the problem has focused on two approaches to settle the question of whether such an improvement is possible: the development of algorithms that improve on unstructured sorting in their number of comparisons rather than in their total running time, and lower bounds for the number of comparisons based on counting cells in subdivisions of high-dimensional spaces. Both approaches are historically tied together, in that the first algorithms that used few comparisons were based on the weakness of the cell-counting lower bounds.

Problem statement and history

The input to the [math]\displaystyle{ X+Y }[/math] sorting problem consists of two finite collections of numbers [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math], of the same length. The problem's output is the collection of all pairs of a number from [math]\displaystyle{ X }[/math] and a number from [math]\displaystyle{ Y }[/math], arranged into sorted order by the sum of each pair. As a small example, for the inputs [math]\displaystyle{ X=\{1,2,9\} }[/math] and [math]\displaystyle{ Y=\{0,4,9\} }[/math], the output should be the list of pairs[math]\displaystyle{ (1,0),\, (2,0),\, (1,4),\, (2,4),\, (9,0),\, (1,9),\, (2,9),\, (9,4),\, (9,9) }[/math]of one element from [math]\displaystyle{ X }[/math] and one element from [math]\displaystyle{ Y }[/math], listed in sorted order by their sums of pairs[math]\displaystyle{ 1, 2, 5, 6, 9, 10, 11, 13, 18. }[/math]One way to solve the problem would be to construct the pairs to be sorted (the Cartesian product of the two collections) and use these pairs as input to a standard comparison sorting algorithm such as merge sort or heapsort. When the inputs have length [math]\displaystyle{ n }[/math], they form [math]\displaystyle{ n^2 }[/math] pairs, and the time to sort the pairs in this way is [math]\displaystyle{ O(n^2\log n) }[/math]. In terms of its big O notation, this method is the fastest known algorithm for [math]\displaystyle{ X+Y }[/math] sorting. Whether a faster algorithm exists is an open problem, posed by Elwyn Berlekamp prior to 1975.

A variant of the problem sorts the sumset, the set of sums of pairs, with duplicate sums condensed to a single value. For this variant, the size of the sumset may be significantly smaller than [math]\displaystyle{ n^2 }[/math], and output-sensitive algorithms for constructing it have been investigated.

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 both the cost of each hop and which pairs of hops may be combined into a single ticket. Skiena's solution consists of sorting pairs of hops by their total cost as an instance of the [math]\displaystyle{ X+Y }[/math] 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 [math]\displaystyle{ (x,y) }[/math] is removed from the queue and found to be disallowed, two more pairs are added, with one of these two pairs combining [math]\displaystyle{ x }[/math] with the next hop after [math]\displaystyle{ y }[/math] in a sorted list of the hops to the destination, and the other pair combining [math]\displaystyle{ y }[/math] with the next hop after [math]\displaystyle{ x }[/math] 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.

[math]\displaystyle{ X+Y }[/math] sorting is the most expensive subroutine in an algorithm for a problem in VLSI design, in which one must place two subunits of a VLSI circuit side-by-side along a communications channel in order to minimize the width of the channel needed to route pairs of wires from one subunit to the other. As one subunit is continuously shifted relative to the other, the channel width only changes at discrete positions where the ends of two wires line up with each other, and finding the sorted ordering of these positions in order to compute the sequence of changes to the width can be performed by [math]\displaystyle{ X+Y }[/math] sorting. If this sorting problem could be sped up, it would also speed up this VLSI design task.

Another application involves polynomial multiplication for polynomials of a single variable that may have many fewer terms than their degrees. The product of two polynomials can be expressed as a sum of products of pairs of terms, one from each polynomial, and placing these term-by-term products into degree order amounts to sorting them by the sum of degrees. For example, the instance of [math]\displaystyle{ X+Y }[/math] sorting with [math]\displaystyle{ n=3 }[/math] given as an example above corresponds to the multiplication of two three-term polynomials to produce a nine-term polynomial: [math]\displaystyle{ \begin{align} (&x+x^2+x^9)(1+x^4+x^9)\\ &=x+x^2+x^5+x^6+x^9+x^{10}+x^{11}+x^{13}+x^{18}.\\ \end{align} }[/math] The degrees are always integers, so integer-based algorithms for [math]\displaystyle{ X+Y }[/math] sorting may be applied. However, for polynomials whose number of terms is comparable to their degree, FFT-based polynomial multiplication algorithms may be significantly more efficient than term-by-term multiplication.

Number of orderings

A well-known lower bound for unstructured sorting, in the decision tree model, is based on the factorial number of sorted orders that an unstructured list may have. Because each comparison can at best reduce the number of possible orderings by a factor of two, sorting requires a number of comparisons at least equal to the binary logarithm of the factorial, which is [math]\displaystyle{ n\log_2 n-O(n) }[/math]. Early work on [math]\displaystyle{ X+Y }[/math] sorting followed a similar approach by asking how many different sorted orderings are possible for this problem, and proving that this number is at most [math]\displaystyle{ O(n^{8n}) }[/math]. However, because its binary logarithm is at most [math]\displaystyle{ 8n\log_2 n+O(1) }[/math], much smaller than the known time bounds for [math]\displaystyle{ X+Y }[/math] sorting, this method can only lead to weak lower bounds on the number of comparisons.

The proof of this bound relates [math]\displaystyle{ X+Y }[/math] sorting to the complexity of an arrangement of hyperplanes in high-dimensional geometry. The two input collections for the [math]\displaystyle{ X+Y }[/math] sorting problem comprise [math]\displaystyle{ 2n }[/math] numbers, which can alternatively be interpreted as the Cartesian coordinates of a point in the [math]\displaystyle{ 2n }[/math]-dimensional space [math]\displaystyle{ \mathbb{R}^{2n} }[/math]. This space can be subdivided into cells, so that within a single cell all points correspond to inputs that produce the same sorted order. For this subdivision, each boundary between two cells lies within a hyperplane defined by an equality of pairs [math]\displaystyle{ x_i+y_j=x_k+y_\ell }[/math], where [math]\displaystyle{ (x_i,y_j) }[/math] and [math]\displaystyle{ (x_k,y_\ell) }[/math] 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 [math]\displaystyle{ x_i=x_k }[/math] or [math]\displaystyle{ y_j=y_\ell }[/math], so the number of distinct hyperplanes that can be determined in this way is [math]\displaystyle{ k=2\binom{n}{2}^2+2\binom{n}{2}. }[/math] The number of cells that this number of hyperplanes can divide a space of dimension [math]\displaystyle{ 2n }[/math] into is [math]\displaystyle{ \binom{k}{2n}+\binom{k}{2n-1}+\cdots+\binom{k}{0}=O(n^{8n}). }[/math] Therefore, the set [math]\displaystyle{ X+Y }[/math] has [math]\displaystyle{ O(n^{8n}) }[/math] different possible sorted orderings.

A similar style of analysis has been more successful in ruling out fast solutions to certain generalizations of [math]\displaystyle{ X+Y }[/math] sorting, by showing that they have too many orderings to sort quickly. In particular, (Harper Payne) suggest separately sorting [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math], and then constructing a two-dimensional matrix of the values of [math]\displaystyle{ X+Y }[/math] that is sorted both by rows and by columns before using this partially-sorted data to complete the sort of [math]\displaystyle{ X+Y }[/math]. This idea of using a row-sorted and column-sorted matrix forms the basis for the method used by Skiena in the transportation application, and it can reduce the number of comparisons by a constant factor relative to naive comparison sorting. However, for matrices whose rows and columns are sorted in this way, the number of possible sorted orderings of the whole matrix is much larger than [math]\displaystyle{ O(n^{8n}) }[/math], so large that any comparison sorting algorithm that can work for arbitrary [math]\displaystyle{ n\times n }[/math] matrices that are sorted by rows and columns still requires [math]\displaystyle{ \Omega(n^2\log n) }[/math] comparisons. Therefore, if the [math]\displaystyle{ X+Y }[/math] sorting problem is to be solved quickly, the solution must use additional information about the set [math]\displaystyle{ X+Y }[/math] beyond this matrix ordering.

Number of comparisons

For the classical comparison sorting problem, the time to sort and the number of comparisons needed to sort are within constant factors of each other. But for [math]\displaystyle{ X + Y }[/math] sorting, the number of comparisons is smaller than the best time bound known: Michael Fredman showed in 1976 that [math]\displaystyle{ X + Y }[/math] sorting can be done using only [math]\displaystyle{ O(n^2) }[/math] comparisons. More generally, he showed that any set of [math]\displaystyle{ N }[/math] elements, whose sorted ordering has already been restricted to a family [math]\displaystyle{ \Gamma }[/math] of orderings, can be sorted using [math]\displaystyle{ \log_2|\Gamma|+O(N) }[/math] comparisons, by a form of binary insertion sort. For the [math]\displaystyle{ X + Y }[/math] sorting problem, [math]\displaystyle{ N=n^2 }[/math], and [math]\displaystyle{ |\Gamma|=O(n^{8n}) }[/math], so [math]\displaystyle{ \log_2|\Gamma|=O(n\log n) }[/math] and Fredman's bound implies that only [math]\displaystyle{ O(n^2) }[/math] comparisons are needed. However, in Fredman's method, the time needed to decide which comparisons to perform may be significantly higher than the bound on the number of comparisons.

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

1. Recursively sort the two sets [math]\displaystyle{ X+X }[/math] and [math]\displaystyle{ Y+Y }[/math].
2. Use the equivalence [math]\displaystyle{ x_i-x_j\le x_k-x_\ell \Leftrightarrow x_i+x_\ell\le x_j+x_k }[/math] to infer the sorted orderings of [math]\displaystyle{ X-X }[/math] and [math]\displaystyle{ Y-Y }[/math] without additional comparisons.
3. Merge the two sets [math]\displaystyle{ X-X }[/math] and [math]\displaystyle{ Y-Y }[/math] into a single sorted order, using a number of comparisons linear in their total size.
4. Use the merged order and the equivalence [math]\displaystyle{ x_i+y_j\le x_k+y_\ell\Leftrightarrow x_i-x_k\le y_\ell-y_j }[/math] to infer the sorted order of [math]\displaystyle{ X+Y }[/math] without additional comparisons.

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

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

The number of comparisons [math]\displaystyle{ C(n) }[/math] needed to perform this recursive algorithm on an input of [math]\displaystyle{ n }[/math] items can be analyzed using the recurrence relation [math]\displaystyle{ C(n)\le 2C(n/2)+O(n^2), }[/math] where the [math]\displaystyle{ 2C(n/2) }[/math] term of the recurrence counts the number of comparisons in the recursive calls to the algorithm to sort [math]\displaystyle{ A+A }[/math] and [math]\displaystyle{ B+B }[/math], and the [math]\displaystyle{ O(n^2) }[/math] term counts the number of comparisons used to merge the results. The master theorem for recurrence relations of this form shows that [math]\displaystyle{ C(n)=O(n^2). }[/math] The total time complexity is slower, [math]\displaystyle{ O(n^2\log n) }[/math], 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 [math]\displaystyle{ O(n^2\log n) }[/math] by using a standard comparison-sorting algorithm with its comparison steps replaced by the stated inferences.

If only comparisons between elements of [math]\displaystyle{ X+Y }[/math] are allowed, then there is also a matching lower bound of [math]\displaystyle{ \Omega(n^2) }[/math] on the number of comparisons, but with more general comparisons involving linear combinations of constant numbers of elements, only [math]\displaystyle{ O(n\log^2 n) }[/math] comparisons are needed.

Non-comparison-based algorithms

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

Related problems

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

The problem of testing whether two of the pairs in the [math]\displaystyle{ X+Y }[/math] 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.