An Explicit and Efficient $O(n^2)$-Time Algorithm for Sorting Sumsets

S. Mundhra

We present the first explicit comparison-based algorithm that sorts the sumset $X+Y=\{x_i+y_j,\forall 0\le i,j<n\}$, where $X$ and $Y$ are sorted arrays of real numbers…