X + Y sorting
|Unsolved problem in computer science:|
Is there an X + Y sorting algorithm faster than ?(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.
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.
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.
- Harper, L. H.; Payne, T.H.; Savage, J. E.; Straus, E. (1975). "Sorting X + Y". Communications of the ACM. 18 (6): 347–349. doi:10.1145/360825.360869.
- Demaine, Erik; Erickson, Jeff; O'Rourke, Joseph (20 August 2006). "Problem 41: Sorting X + Y (Pairwise Sums)". The Open Problems Project. Retrieved 23 September 2014.
- Skiena, Steven (2008). The Algorithm Design Manual. Springer. p. 119. doi:10.1007/978-1-84800-070-4_4.
- Fredman, Michael L. (1976). "How good is the information theory bound in sorting?". Theoretical Computer Science. 1 (4): 355–361. doi:10.1016/0304-3975(76)90078-5.
- Lambert, Jean-Luc (1992). "Sorting the sums (xi + yj) in O(n2) comparisons". Theoretical Computer Science. 103 (1): 137–141. doi:10.1016/0304-3975(92)90089-X.