Учитывая отсортированный массив целых чисел, можем ли мы построить отсортированный массив сумм всех пар в O (n ^ 2)?
Тривиальным решением было бы построить массив сумм в O (n ^ 2), а затем отсортировать его в O (n ^ 2 (log (n ^ 2)) = O (n ^ 2 logn) времени.
Другим решением было бы построить n отсортированных массивов из n чисел каждый - в O (n ^ 2) и объединить их в O (n ^ 2 logn) времени (см. здесь).
Можем ли мы сделать лучше?
