X + Y sorting

In computer science, X + Y sorting is the problem of sorting pairs of numbers by their sum. Given two finite sets  and , the problem is to order all pairs  in the Cartesian product  by the key . The problem is attributed to Elwyn Berlekamp.

Time for comparison algorithms

This problem can be solved using a straightforward comparison sort on the Cartesian product, taking time  for sets of sizes  and . When it is assumed that , the complexity of this method is , which is also the best upper bound known on the time for this problem.  Whether X + Y sorting can be done strictly faster than sorting  arbitrary numbers is an open problem.

Number of comparisons
The number of required comparisons is certainly lower than for ordinary comparison sorting: Fredman showed, in 1976, that X + Y sorting can be done using only  comparisons, though he did not show an algorithm. The first actual algorithm that achieves this number of comparisons and  total complexity was published sixteen years later.

Non-comparison-based algorithms
On a RAM machine with word size  and integer inputs , the problem can be solved in  operations by means of the fast Fourier transform.

Applications
Skiena recounts a practical application in transit fare minimisation, an instance of the shortest path problem: given fares  and  for trips from departure A to some intermediate destination B and from B to final destination C, determine the least expensive combined trip from A to C.

See also
 3SUM
 Integer sorting

References

Category:Sorting algorithms
Category:Unsolved problems in computer science