X + Y sorting

Unsolved problem in computer science:
Is there an X + Y sorting algorithm faster than 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 n⋅m 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]

See also

References

  1. 1 2 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.
  2. 1 2 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.
  3. 1 2 Skiena, Steven (2008). The Algorithm Design Manual. Springer. p. 119. doi:10.1007/978-1-84800-070-4_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.
  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.
This article is issued from Wikipedia - version of the Monday, August 10, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.