<p>You can do this in two lines in python with</p>
<pre><code>allSums = set(a+b for a in X for b in X)
allSums = sorted(allSums)
</code></pre>
<p>The cost of this is <code>n^2</code> (maybe an extra log factor for the set?) for the iteration and s * log(s) for the sorting where s is the size of the set.</p>
<p>The size of the set could be as big as <code>n*(n-1)/2</code> for example if <code>X = [1,2,4,...,2^n]</code>. So if you want to generate this list it will take at least <code>n^2/2</code> in the worst case since this is the size of the output.</p>
<p>However if you want to select the first k elements of the result you can do this in O(kn) using a selection algorithm for sorted <code>X+Y</code> matrices by Frederickson and Johnson (<a href="http://arxiv.org/abs/0804.0936" rel="nofollow noreferrer">see here for gory details)</a>. Although this can probably be modified to generate them online by reusing computation and get an efficient generator for this set.</p>
<p>@deuseldorf, Peter
There is some confusion about <code>(n!)</code> I seriously doubt deuseldorf meant &quot;n factorial&quot; but simply &quot;n, (very excited)!&quot;</p>
Efficiently get sorted sums of a sorted list
<p>You have an ascending list of numbers, what is the most efficient algorithm you can think of to get the ascending list of sums of every two numbers in that list.  Duplicates in the resulting list are irrelevant, you can remove them or avoid them if you like.</p>

<p>To be clear, I'm interested in the algorithm.  Feel free to post code in any language and paradigm that you like.</p>