Storing pairwise sums in linear space

Question

If we have two arrays of size n each and want to sort their sums, the naive approach would be to store their sums in O(n^2) space and sort it in O(n^2 logn) time. Suppose we're allowed to have the same running time of O(n^2 logn), how would we store the sums in linear space of O(n)?

I suppose we're not intending to store all the sums since they n^2 elements won't fit into n space and that we're merely printing out everything in sorted order, so does this mean that we have to dynamically store the items? Any tips?

(this is a homework problem)

Answer 1

The problem, as I understand it, is that we want to find the sums

a1 + b1  a1 + b2  ...  a1 + bn
a2 + b1  a2 + b2  ...  a2 + bn
  ...      ...    ...    ...
an + b1  an + b2  ...  an + bn

and print them in sorted order. The restriction is to use only O (n) memory and O (n^2 log n) time in the process.

Consider the above table as n lists (lines) of n elements each. If we sort the initial arrays so that a1 <= a2 <= ... <= an and b1 <= b2 <= ... <= bn, each list is already sorted. Now, the problem is reduced to merging n sorted lists.

To devise that, think of how to merge two sorted lists (as in MergeSort), then three lists, and so on. This extends trivially to merging n lists of length n each in n operations for each output element, for a total of O (n^3). Now, what's left is to reduce time for getting each output element down to O (log n). As you ask for a hint but not a complete solution, see if you can handle that step yourself.