efficient sorted Cartesian product of 2 sorted array of integers

If there's a solution that's better than O(n² log n) it needs to do more than just exploit the fact that A and B are already sorted. See my answer to this question.

Srikanth wonders how this can be done in O(n) space (not counting the space for the output). This can be done by generating the lists lazily.

Suppose we have A = 6,7,8 and B = 3,4,5. First, multiply every element in A by the first element in B, and store these in a list:

6×3 = 18, 7×3 = 21, 8×3 = 24

Find the smallest element of this list (6×3), output it, replace it with that element in A times the next element in B:

7×3 = 21, 6×4 = 24, 8×3 = 24

Find the new smallest element of this list (7×3), output it, and replace:

6×4 = 24, 8×3 = 24, 7×4 = 28

And so on. We only need O(n) space for this intermediate list, and finding the smallest element at each stage takes O(log n) time if we keep the list in a heap.

If you multiply a value of A with all values of B, the result list is still sorted. In your example:

A is 1, 3, 5

B is 4, 8, 10

1*(4,8,10) = 4,8,10

3*(4,8,10) = 12,24,30

Now you can merge the two lists (exactly like in merge sort). You just look at both list heads and put the smaller one in the result list. so here you would select 4, then 8 then 10 etc.result = 4,8,10,12,24,30

Now you do the same for result list and the next remaining list merging 4,8,10,12,24,30 with 5*(4,8,10) = 20,40,50.

As merging is most efficient if both lists have the same length, you can modify that schema by dividing A in two parts, do the merging recursively for both parts, and merge both results.

Note that you can save some time using a merge approach as is isn't required that A is sorted, just B needs to be sorted.