In [this question](https://mathoverflow.net/questions/39386/number-of-unique-sortings-of-subset-sums) the number of unique sortings has been discussed. 


As a follow-up, I would like to know, whether the problem of sorting the sequence of subset sums has ever been studied.  

There should different algorithms for the case of only positive element-weights and for positive and negative element weights. 


In analogy to the "ordinary" sorting problem, I would expect a variety of solutions to exist, addressing either simplicity of formulation (Bubblesort),
practical applicability (Quicksort) and worst-case optimality (Heapsort). 



> 
> **Question::**  
> 
>  is there a technical term for the problem and, what would be good ressources for it?
> 
> 
> 



Algorithms for Sorting Subset Sums
One standard situation where sorted subset sums comes up is in the [subset sum problem](https://en.wikipedia.org/wiki/Subset_sum_problem). (I.e. is zero among the subset sums of a given set?) By splitting the input into two equinumerous subsets, sorting the subset sums of each subset, and comparing the two lists of sorted subset sums, it is possible to solve the problem in time proportional to roughly $2^{n/2}$ (where $n$ is the number of given values) rather than the naive bound of $2^n$.


According to Wikipedia this idea is due to Horowitz and Sahni in 1972; see the link for references.


As for your idea that all-positive should be easier than unconstrained values: I don't think so. If you add the same large value to all inputs, it makes them all positive without changing the solution much (you can decompose the result into a linear number of subsequences within which all sums have been changed in the same way, then merge these subsequences to get the sorted order of your original input, only increasing the complexity by a small amount).


