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(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 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(n2) comparisons, though he did not show an algorithm. The first actual algorithm that achieves this number of comparisons and O(n2 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 = 2w, 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.