Subset sum exponential solution - how does the sorting work?
The idea is that two sorted lists of length $n$ can be merged into one sorted list of length $2n$ in time $O(n)$. This is a standard procedure used in the mergesort algorithm. Given a list of integers $x_1,\ldots,x_m$, you proceed as follows:


Start with $A_0 = 0$.
Merge $A_0$ and $A_0 + x_1$ into $A_1$.
Merge $A_1$ and $A_1 + x_2$ into $A_2$.
...
Merge $A_{m-1}$ and $A_{m-1} + x_m$ into $A_m$.
Output $A_m$.


Here $A_k + x_{k+1}$ is formed by adding $x_{k+1}$ to all elements of $A_k$, preserving the order.

Since $A_k$ has length $2^k$, the total running time is
$$
O(|A_0| + |A_1| + \cdots + |A_{m-1}|) = O(1 + 2 + \cdots + 2^{m-1}) = O(2^m).
$$