The best I could come up with is to produce a matrix of sums of each pair, and then merge the rows together, a-la merge sort. I feel like I'm missing some simple insight that will reveal a much more efficient solution.

My algorithm, in Haskell:

`matrixOfSums list = [[a+b | b <- list, b >= a] | a <- list]`

sortedSums = foldl merge [] matrixOfSums

--A normal merge, save that we remove duplicates

merge xs [] = xs

merge [] ys = ys

merge (x:xs) (y:ys) = case compare x y of

LT -> x:(merge xs (y:ys))

EQ -> x:(merge xs (dropWhile (==x) ys))

GT -> y:(merge (x:xs) ys)

I found a minor improvement, one that's more amenable to lazy stream-based coding. Instead of merging the columns pair-wise, merge all of them at once. The advantage being that you start getting elements of the list immediately.

`-- wide-merge does a standard merge (ala merge-sort) across an arbitrary number of lists`

-- wideNubMerge does this while eliminating duplicates

wideNubMerge :: Ord a => [[a]] -> [a]

wideNubMerge ls = wideNubMerge1 $ filter (/= []) ls

wideNubMerge1 [] = []

wideNubMerge1 ls = mini:(wideNubMerge rest)

where mini = minimum $ map head ls

rest = map (dropWhile (== mini)) ls

betterSortedSums = wideNubMerge matrixOfSums

However, if you know you're going to use all of the sums, and there's no advantage to getting some of them earlier, go with '`foldl merge []`

', as it's faster.