X + Y sorting

Open problem in computer science: Is there an X + Y sorting algorithm faster than $O(n^2 \log n)$? (more open problems in computer science)

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

This problem can be solved using a straightforward comparison sort on the Cartesian product, taking time O(nm log(nm)) for sets of sizes n and m. When it is assumed that m = n, the complexity is O(n² log n²) = O(n² log n), which is also the best known bound on the problem, but whether X + Y sorting can be done strictly faster than sorting n⋅m arbitrary numbers is an open problem. 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 O(n²) comparisons, though he did not show an algorithm. The first actual algorithm that achieves this number of comparisons and O(n² log n) total complexity was only published sixteen years later.

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.

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, determine the least expensive combined trip from A to C.

See also

• 3SUM
• Integer sorting