There are $$$m$$$ positive integers that add up to $$$n$$$. On each step take any two numbers, add the minimum of the two to the result and replace those two numbers with their sum (the size of the number set decreases by one). Repeat that until there is only one number left. Why is the result at most $$$n \log_2 n$$$? I have proof below which I don't know is correct or not. But I want to understand the intuition behind this one. Is there somewhere where I could read about this?

My idea is to use induction and see for myself that for small $$$n$$$ this works. Look at the last merge, we will have $$$n_1$$$ and $$$n_2$$$ such that $$$n_1+n_2=n$$$ and $$$n_1 \leq n_2$$$. By induction, the result by now is at most $$$n_1 \log n_1 + n_2 \log n_2$$$. We want to prove that $$$n_1 \log n_1 + n_2 \log n_2 + n_1 \leq n \log n$$$. To see that we can define $$$k = \frac{n_1}{n} \leq \frac 1 2$$$. We now want to prove:

But we know that $$$k \leq \frac 1 2$$$ meaning $$$\log k \leq -1$$$ and hence $$$1 + \log k \leq 0$$$ and now it's clear that both summands in the last line are at most 0.