I have found that 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?

  • $\begingroup$ According to wikipedia it is $\endgroup$ – nir shahar May 30 at 21:01

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.