patternMinor
Is X+Y sorting problem still an open problem?
Viewed 0 times
sortingopenproblemstill
Problem
I have found that
Is there any algorithm proposed that can solve it in O(n2) comparison or
X + Y sorting is an open computer science problem but that book was too old and then I have google it but didn't find any strong evidence that it is still open or there is an algorithm that can solve it in O(n2) comparison without using Fast Fourier Transform.Is there any algorithm proposed that can solve it in O(n2) comparison or
is it still unsolved?Solution
Here the problem status is "open". The page was revised in 2006 and it seems updated to September 2017, so we can safely suppose that the problem is still open.
Anyway, an algorithm that solves the problem using $O(n^2)$ comparison (and total complexity $O(n^2\cdot \log(n))$) is known from 1992: J.-L. Lambert, Sorting the sums $x_i+y_j$ in $O(n^2)$ comparisons, Theoretical Computer Science, (1992):103, 137–141 doi 10.1016/0304-3975(92)90089-X.
Anyway, an algorithm that solves the problem using $O(n^2)$ comparison (and total complexity $O(n^2\cdot \log(n))$) is known from 1992: J.-L. Lambert, Sorting the sums $x_i+y_j$ in $O(n^2)$ comparisons, Theoretical Computer Science, (1992):103, 137–141 doi 10.1016/0304-3975(92)90089-X.
Context
StackExchange Computer Science Q#126526, answer score: 3
Revisions (0)
No revisions yet.