Given a sorted array, can we build a sorted array of the sums of all pairs in O(n^2)?
algorithm, sorting
Solution
This is an open problem known in the literature as Sorting X + Y. The best result known is an O(n^2 log n)-time algorithm that uses O(n^2) comparisons, due to Lambert and Steiger--Streinu.
Problem
Given a sorted array of integers, can we build a sorted array of the sums of all pairs in O(n^2)? A trivial solution would be to build the array of sums in O(n^2) and then to sort it in O(n^2 (log(n^2)) = O(n^2 logn) time. Another solution would be to build n sorted arrays of n numbers each - in O(n^2), and merge them in O(n^2 logn) time (see here for example). Can we do better?