эффективное отсортированное декартово произведение 2 отсортированных массивов целых чисел

Требуются Подсказки для разработки эффективного алгоритма, который принимает следующие входные данные и выводит следующий результат .

Вход: два отсортированных массива целых чисел A и B, каждый длиной n

Выход: Один отсортированный массив, который состоит из декартова произведения массивов A и B.

For Example: 

Input:
A is 1, 3, 5
B is 4, 8, 10
here n is 3.

Output:
4, 8, 10, 12, 20, 24, 30, 40, 50

Вот мои попытки решить эту проблему.

1) Учитывая, что вывод n ^ 2, эффективный алгоритм не может работать лучше, чем временная сложность O (n ^ 2).

2) Сначала я попробовал простой, но неэффективный подход. Сгенерируйте декартово произведение A и B. Это можно сделать за O (n ^ 2) временной сложности. нам нужно хранить, поэтому мы можем выполнять по нему сортировку. Следовательно, сложность пространства O (n ^ 2) тоже. Теперь мы сортируем n ^ 2 элементов, что невозможно сделать лучше, чем O (n ^ 2logn), без каких-либо предположений о вводе.

Наконец, у меня есть время O (n ^ 2logn) и пространство O (n ^ 2) алгоритм сложности.

Должен быть алгоритм получше, потому что я не использовал сортированный характер входных массивов.