X + Y sorting

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.

sorting problem consists of two finite collections of numbers

In terms of its big O notation, this method is the fastest known algorithm for

Whether a faster algorithm exists is an open problem,[1][2] posed by Elwyn Berlekamp prior to 1975.

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

in a sorted list of the hops to the destination, and the other pair combining

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

If this sorting problem could be sped up, it would also speed up this VLSI design task.

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

sorting, this method can only lead to weak lower bounds on the number of comparisons.

numbers, which can alternatively be interpreted as the Cartesian coordinates of a point in the

For this subdivision, each boundary between two cells lies within a hyperplane defined by an equality of pairs

[3][9][10] A similar style of analysis has been more successful in ruling out fast solutions to certain generalizations of

[3] This idea of using a row-sorted and column-sorted matrix forms the basis for the method used by Skiena in the transportation application,[2] and it can reduce the number of comparisons by a constant factor relative to naive comparison sorting.

sorting problem is to be solved quickly, the solution must use additional information about the set

sorting, the number of comparisons is smaller than the best time bound known: Michael Fredman showed in 1976 that

total complexity was published sixteen years after Fredman by Lambert (1992).

term of the recurrence counts the number of comparisons in the recursive calls to the algorithm to sort

The master theorem for recurrence relations of this form shows that

, because of the steps of the algorithm that use already-made comparisons to infer orderings of other sets.

by using a standard comparison-sorting algorithm with its comparison steps replaced by the stated inferences.

[1][3] Several other problems in computational geometry have equivalent or harder complexity to

-coordinates, listing pairs of points in sorted order by their distances, and testing whether one rectilinear polygon can be translated to fit within another.

In turn, it could be used to solve the 3SUM problem, implying that it is unlikely to have a strongly subquadratic algorithm.