HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is X+Y sorting problem still an open problem?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
sortingopenproblemstill

Problem

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?

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.

Context

StackExchange Computer Science Q#126526, answer score: 3

Revisions (0)

No revisions yet.