# X + Y sorting

 Unsolved problem in computer science:Is there an X + Y sorting algorithm faster than ${\displaystyle O(n^{2}\log n)}$?(more unsolved 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.[1][2]

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(n2 log n2) = O(n2 log n), which is also the best known bound on the problem, but whether X + Y sorting can be done strictly faster than sorting nm arbitrary numbers is an open problem.[3][2] 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(n2) comparisons, though he did not show an algorithm.[4] The first actual algorithm that achieves this number of comparisons and O(n2 log n) total complexity was only published sixteen years later.[5]

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

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