Given a sorted array, can we build a sorted array of the sums of all pairs in O(n^2)?

Question

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?

Answer 1

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.